用链表兑现线性表的各种操作(C语言)

用链表实现线性表的各种操作(C语言)

#include <stdio.h> # include <malloc.h> # include <stdlib.h> //定义节点结构体 typedef struct Node { int data;//数据域 struct Node * pNext;//指针域 }NODE,* PNODE; //函数声明 PNODE create_list(void); //创建链表 void traverse_list(PNODE pHead);//遍历链表 bool is_empty(PNODE pHead);//判断链表是否为空 int length_list(PNODE);//计算链表的长度 bool insert_list(PNODE, int, int);//插入数据 bool delete_list(PNODE, int, int *);//删除数据 void sort_list(PNODE); //链表排序 int main(void) { PNODE pHead=create_list(); traverse_list(pHead); // printf("%d\n",length_list(pHead)); //insert_list(pHead,3 ,100); //traverse_list(pHead); // int val; // delete_list(pHead,2,&val); //traverse_list(pHead); sort_list(pHead); traverse_list(pHead); return 0; } //创建链表函数实现 PNODE create_list(void) { int len;//存放有效节点的个数 int i; int val ; //临时存放用回输入的节点的值 //创建头结点 PNODE pHead =(PNODE)malloc(sizeof(NODE)); if(NULL==pHead) { printf("分配内存失败,程序终止\n"); exit(-1); } PNODE pTail = pHead;//定义一个临时指针始终指向最后一个节点，辅助指针思想方法 pTail->pNext=NULL; printf("请输入要生成的节点的个数：len="); scanf("%d",&len); for(i=0;i<len;i++) { printf("请输入第%d个节点的值：",i+1); scanf("%d",&val); PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(NULL==pNew) { printf("分配失败，程序终止\n"); exit(-1); } pNew->data=val; pTail->pNext=pNew; pNew->pNext=NULL; pTail=pNew;//注意点 pTail要移动 } return pHead; } //遍历链表 void traverse_list(PNODE pHead) { PNODE p = pHead->pNext; while (NULL != p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); return; } bool is_empty(PNODE pHead)//判断链表是否为空 { if(NULL==pHead->pNext) return true; else return false; } //计算链表的长度 int length_list(PNODE pHead) { int i=0; PNODE p=pHead->pNext; while(NULL!=p) { i++; p=p->pNext; } return i; } //插入数据 bool insert_list(PNODE pHead , int pos , int val) { PNODE p=pHead; if(pos>0&&pos<=(length_list(pHead)+1)) { for( int i=0;i<pos-1;i++) { p=p->pNext; } PNODE pNew = (PNODE)malloc(sizeof(NODE)); pNew->data=val; PNODE temp=p->pNext; p->pNext=pNew; pNew->pNext=temp; return true; } else { return false; } } //删除数据 bool delete_list(PNODE pHead,int pos ,int *pVal) { PNODE p=pHead; if(pos>0&&pos<=(length_list(pHead))) { for( int i=1;i<pos;i++) { p=p->pNext; } PNODE temp=p->pNext->pNext; *pVal=p->pNext->data; p->pNext=temp; return true; } else { return false; } } //链表排序 void sort_list(PNODE pHead) { PNODE p=pHead; for(p=pHead->pNext;p!=NULL;p=p->pNext) { for(PNODE q=p->pNext;q!=NULL;q=q->pNext) { if(q->data<p->data) { int temp=p->data; p->data=q->data; q->data=temp; } } } }

排序还可以用这种算法

 

void sort_list(PNODE pHead) { int i, j, t; int len = length_list(pHead); PNODE p, q; for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext) { for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext) { if (p->data > q->data) //类似于数组中的: a[i] > a[j] { t = p->data;//类似于数组中的: t = a[i]; p->data = q->data; //类似于数组中的: a[i] = a[j]; q->data = t; //类似于数组中的: a[j] = t; } } } return; }
数据插入还可用这种算法

 

bool insert_list(PNODE pHead, int pos, int val) { int i = 0; PNODE p = pHead; while (NULL!=p && i<pos-1) { p = p->pNext; ++i; } if (i>pos-1 || NULL==p) return false; PNODE pNew = (PNODE)malloc(sizeof(NODE)); if (NULL == pNew) { printf("动态分配内存失败!\n"); exit(-1); } pNew->data = val; PNODE q = p->pNext; p->pNext = pNew; pNew->pNext = q; return true; }
数据删除还可用这种算法

 

bool delete_list(PNODE pHead, int pos, int * pVal) { int i = 0; PNODE p = pHead; while (NULL!=p->pNext && i<pos-1) { p = p->pNext; ++i; } if (i>pos-1 || NULL==p->pNext) return false; PNODE q = p->pNext; *pVal = q->data; //删除p节点后面的结点 p->pNext = p->pNext->pNext; free(q); q = NULL; return true; }