线性链表的实现

1、头文件及函数引用：//--------------------------颍骈城茇----------------------------------------------#include<稆糨孝汶;stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct Node{ int data; struct Node *next;}list,*plist;//创建空链表plist creatHead(); //ok//初始化链表plist creatList(plist head); // ok//遍历void traverseList(plist head); // ok//判断是否为空bool isEmpty(plist head); // ok//获取链表的长度int getLength(plist head); //ok//对链表进行排序void sortList(plist head); //ok//在链表中插入元素bool insertList(plist head,int position,int value); //ok//删除链表中的元素bool deleteList(plist head,int position,int *value); // 0k//分配内存的方法,相当于newplist oS(); //ok//未分配到内存报错方法void er(); //ok//------------------------------------------------------------------------

2、主函数：//入口函数void main(){ plist head=creatHead(); if(isEmpty(head)) printf("该链表为空"); else printf("该链表不为空\n"); head=creatList(head); printf("创建后的链表为\n"); traverseList(head); printf("排序后的链表为：\n\n"); sortList(head); if(isEmpty(head)) printf("该链表为空"); else printf("该链表不为空\n"); printf("该链表的长度为:%d\n\n",getLength(head)); insertList(head,2,124); printf("插入元素后的链表为：\n\n"); traverseList(head); int value; deleteList(head,2,&value); printf("删除元素后的链表为：\n\n"); printf("删除的元素为%d\n",value); traverseList(head);}//入口函数结束

3、函数体：plist creatHead(){ plist head=oS(); if(head==NULL) er(); head->next=NULL; return head;}plist oS()//obtainSpace{ plist p=(plist)malloc(sizeof(list)); if(p == NULL) er(); return p;}bool isEmpty(plist head){ if(head->next == NULL) return true; else return false;}plist creatList(plist head){ plist tail=oS(); tail=head; tail->next=NULL; int i; int value; int len; printf("请输入初始长度:"); scanf("%d",&len); for(i=0;i<len;i++) { plist pnew=oS(); if(pnew== NULL) er(); printf("请输入第%d个元素：",i+1); scanf("%d",&value); pnew->data=value; tail->next=pnew; pnew->next=NULL; tail=pnew; } return head;}void er(){ printf("分配内存失败，即将退出。"); exit(-1);}void traverseList(plist head){ int i=1; if(isEmpty(head)) { printf("该链表为空,无法遍历"); exit(-1); } plist p=head; while(p->next != NULL) { printf("第%d元素为%d:\n",i++,p->next->data); p=p->next; }}int getLength(plist head){ int len=0; plist p=head->next; while(p!=NULL) { len++; p=p->next; } return len;}void sortList(plist head){ int len=getLength(head); int i,j,t; plist p,q; for(i=0,p=head->next;i<len-1;i++,p=p->next) { for(j=i+1,q=p->next;j<len;j++,q=q->next) { if(p->data >q->data) { t=q->data; q->data=p->data; p->data=t; } } }}bool insertList(plist head,int position,int value){ int i=0; plist p=head; while(p != NULL && i<position-1) { p=p->next; i++; } if(p == NULL || i>position-1) { return false; } plist pnew=oS(); if(pnew==NULL) { er(); } plist t=p->next; pnew->data=value; p->next=pnew; pnew->next=t; return true;}bool deleteList(plist head,int position, int *value){ int i=0; plist p=head; while(p!= NULL && i<position-1) { p=p->next; i++; } if(p==NULL || i>position-1) { return false; } plist t=p->next; *value=p->next->data; p->next=p->next->next; free(t); return true;}