结构和指针(单链表部分)

1、结构和指针单链表部分关于单链表的基本操作，包括创建一单链表、查看链表、插入新结点、删除结点、链表逆转以及链表排序。包括两个文件：*List.h*/* *头文件List.h*/#ifndef LIST_H /*防止头文件重复定义*/#define LIST_H/*/* 宏定义 */*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef struct NODEstruct NODE *next;int value; Node;/* 函数的类型定

2、义*/typedef int Status; #endif /* LIST_H */* End Of File */*List.cpp*/* 关于单链表的基本操作，包括创建一单链表、查看链表、插入新结点、* 删除结点、链表逆转以及链表排序。*/*/* 头文件包含 */*/#include #include #include "List.h"/*/* 宏定义 */*/#define LENGTH sizeof(Node/*/* 全局变量定义 */*/Node *list = NULL;/*/* 子函数定义 */*/* 打印输出方法函数*/* 初期化函数*/StatusUse_

3、Method( void printf("|*使用*方法*|n"printf("|* 1 初期化链表*|n"printf("|* 2 创建一链表*|n"printf("|* 3 输出该链表*|n"printf("|* 4 插入结点 *|n"printf("|* 5 删除结点 *|n"printf("|* 6 逆转链表 *|n"printf("|* 7 链表排序 *|n"printf("|* 8 终止程序 *|n"pr

4、intf("|* 输入错误，再输入*|n"return OK; /* Use_Method */StatusInit_List( Node *phead phead = NULL;printf("初期化函数成功！n"return OK; /* Init_List */* 创建链表函数*/Status Create_List(Node *pheadNode *p,*q;/*创建一链表*/printf("|*|n"printf("|*创*建*链*表*|n"printf("|*|n"/*指向第一个结点

5、*/*phead = p = (Node *malloc(LENGTH; /*开辟内存失败*/if( NULL = p return FALSE;printf("请输入第一个结点数据:n"scanf("%d",&p->value;q = p;/*指向第二个结点*/p = (Node *malloc(LENGTH;/*开辟内存失败*/if( NULL = p return FALSE;printf("请输入第二个结点数据:n"/*开辟内存失败*/if( NULL = p return FALSE;scanf("%

6、d",&p->value;q->next = p;q = p;/*指向第三个结点*/p = (Node *malloc(LENGTH;printf("请输入第三个结点数据:n"scanf("%d",&p->value;q->next = p;p->next = NULL;printf("链表创建成功“o”nn"return OK; /* Create_List */* 查看链表函数*/Status Show_List(Node *pheadNode *p = phead;int

7、i = 1;/* 打印输出标题*/if( 1 = i printf("|*|n"printf("|*新建*的*链表*|n"printf("|*|n"elseprintf("|*|n"printf("|*变改*后*的*链表*|n"printf("|*|n"/* 输出链表*/doprintf("%d -> ",p->value;p = p->next;while(p->next != NULL;printf("%dn"

8、;,p->value;i+;return OK; /* Show_List */* 插入结点函数*/Status Insert_List(Node *pheadNode *p,*q;int element;p = *phead;printf("请输入插入结点数据的值:n"scanf("%d",&element;/*p指向第一结点时，就满足要求*/while(p->value > elementNode *s = (Node *malloc(LENGTH;if( NULL = s return FALSE;s->value

9、= element;s->next = p;*phead = s;printf("结点数据插入头结点之前:n"return OK;/*若第一个结点不满足怎继续往下查找*/while(p->value <= elementq = p;p = p->next;/*p指向NULL,就结束循环，防止对p间接访问*/if(p = NULL printf("结点数据插入尾部结点之后:n"break;Node *s = (Node *malloc(LENGTH;if( NULL = s return FALSE;s->value = el

10、ement;s->next = p;q->next = s;return OK; /* Insert_List */* 删除结点函数*/Status Delete_List(Node *phead/*删除结点*/Node *p,*q;int element;p = *phead;printf("请输入删除结点的值:n"scanf("%d",&element;/*第一个结点数据是要删除的数据*/if( element = p->value *phead = p->next;return OK;/*第一结点数据不是要删除的数据

11、*/while(p != NULLif( element = p->value q->next = q->next->next;free(p;return OK;q = p;p = p->next;if( NULL = p printf("没有查找到要删除的节点数据n"return ERROR; /* Delete_List */* 链表逆序输出函数*/Status Reverse_List(Node *phead/*链表逆转输出*/printf("|*链表逆序输出*|n"/*如果链表是空或者只有一个结点*/if( *phe

12、ad = NULL | (*phead->next = NULL return OK;/*链表有两个结点及以上*/Node *p = *phead,*q = (*phead->next,*t = NULL;while( q != NULL t = q->next;q->next = p;p = q;q = t;/*此时p指向原始链表最后一个元素，也是逆转后的链表的表头元素*/(*phead->next = NULL; /*设置链表尾*/*phead = p; /*调整链表头*/return OK; /* Reverse_List */* 链表冒泡法排序*/Stat

13、usSort_List(Node *pheadprintf("链表按从大到小的顺序排序n"/*如果链表是空或者只有一个结点*/if( *phead = NULL | (*phead->next = NULL return OK;/*链表有两个结点及以上*/Node *endp, /*控制循环比较*/*p, /*临时变量*/*p1,*p2;/*新增一个结点*/p1 = (Node *malloc(LENGTH;p1->next = *phead;*phead = p1;for( endp = NULL; endp != *phead; endp = p for(

14、p = p1 = *phead; p1->next->next != endp; p1=p1->next if( p1->next->value > p1->next->next->value /*如果前面的值大于后面的值*/p2 = p1->next->next;p1->next->next = p2->next;p2->next = p1->next;p1->next = p2;p = p1->next->next;/* 把添加的结点去掉*/p1 = *phead;(*phea

15、d = (*phead->next;free(p1;p1 = NULL;return OK; /* Sort_List */int main( void int Options;int i = 0;/* 大循环*/while( 1 Use_Method(; /*给出使用方法*/* 选择功能*/printf("请输入相应命令n"scanf("%d",&Options;switch( Options case 1: /*初期化函数*/Init_List(&list;break;case 2: /*创建一链表*/ Create_List(&list;break;case 3: /*输出该链表*/ Show_List(list;break;case 4: /*插入节点*/ Insert_List(&list;break;case 5: /*删除结点*/Delete_List(&list;break;case 6: /*链表逆转*/Reverse_List(&