线性表的16种算法

1、#include<stdio.h>#include<stdlib.h>typedefintelemType;/*/*以下是关于线性表顺序存储操作的16种算法 */*/structList elemType*list; intsize; intmaxSize;voidagainMalloc(structList*L) /*空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间*/ elemType*p=realloc(L->list,2*L->maxSize*sizeof(elemType); if(!p)/*分配失败则退出运行*/ pr

2、intf("存储空间分配失败！ "); exit(1); L->list=p;/*使list指向新线性表空间*/ L->maxSize=2*L->maxSize;/*把线性表空间大小修改为新的长度*/*1.初始化线性表L，即进行动态存储空间分配并置L为一个空表*/voidinitList(structList*L,intms) /*检查ms是否有效，若无效的则退出运行*/ if(ms<=0) printf("MaxSize非法！ "); exit(1);/*执行此函数中止程序运行，此函数在stdlib.h中有定义*/ L->

3、maxSize=ms;/*设置线性表空间大小为ms*/ L->size=0; L->list=malloc(ms*sizeof(elemType); if(!L->list) printf("空间分配失败！ "); exit(1); return;/*2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表*/voidclearList(structList*L) if(L->list!=NULL) free(L->list); L->list=0; L->size=L->maxSize=0; return;/*3.返回线

4、性表L当前的长度，若L为空则返回*/intsizeList(structList*L) returnL->size;/*4.判断线性表L是否为空，若为空则返回1,否则返回0*/intemptyList(structList*L) if(L->size=0) return1; else return0; /*5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行*/elemTypegetElem(structList*L,intpos) if(pos<1|pos>L->size)/*若pos越界则退出运行*/ printf("元素序号越界！

5、 "); exit(1); returnL->listpos-1;/*返回线性表中序号为pos值的元素值*/*6.顺序扫描（即遍历）输出线性表L中的每个元素*/voidtraverseList(structList*L) inti; for(i=0;i<L->size;i+) printf("%d",L->listi); printf(" "); return;/*7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1*/intfindList(structList*L,elemTypex) inti

6、; for(i=0;i<L->size;i+) if(L->listi=x) returni; return-1;/*8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0*/intupdatePosList(structList*L,intpos,elemTypex) if(pos<1|pos>L->size)/*若pos越界则修改失败*/ return0; L->listpos-1=x; return1;/*9.向线性表L的表头插入元素x*/voidinserFirstList(structList*L,elemTypex)

7、inti; if(L->size=L->maxSize) againMalloc(L); for(i=L->size-1;i>=0;i-) L->listi+1=L->listi; L->list0=x; L->size+; return;/*10.向线性表L的表尾插入元素x*/voidinsertLastList(structList*L,elemTypex) if(L->size=L->maxSize)/*重新分配更大的存储空间*/ againMalloc(L); L->listL->size=x;/*把x插入到表尾*

8、/ L->size+;/*线性表的长度增加*/ return;/*11.向线性表L中第pos个元素位置插入元素x，若插入成功返回，否则返回*/intinsertPosList(structList*L,intpos,elemTypex) inti; if(pos<1|pos>L->size+1)/*若pos越界则插入失败*/ return0; if(L->size=L->maxSize)/*重新分配更大的存储空间*/ againMalloc(L); for(i=L->size-1;i>=pos-1;i-) L->listi+1=L->

9、listi; L->listpos-1=x; L->size+; return1;/*12.向有序线性表L中插入元素x,使得插入后仍然有序*/voidinsertOrderList(structList*L,elemTypex) inti,j; /*若数组空间用完则重新分配更大的存储空间*/ if(L->size=L->maxSize) againMalloc(L); /*顺序查找出x的插入位置*/ for(i=0;i<L->size;i+) if(x<L->listi) break; /*从表尾到下标i元素依次后移一个位置，把i的位置空出来*/

10、 for(j=L->size-1;j>=i;j-) L->listj+1=L->listj; /*把x值赋给下标为i的元素*/ L->listi=x; /*线性表长度增加1*/ L->size+; return;/*13.从线性表L中删除表头元素并返回它，若删除失败则停止程序运行*/elemTypedeleteFirstList(structList*L) elemTypetemp; inti; if(L->size=0) printf("线性表为空，不能进行删除操作！ "); exit(1); temp=L->list0;

11、for(i=1;i<L->size;i+) L->listi-1=L->listi; L->size-; returntemp;/*14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行*/elemTypedeleteLastList(structList*L) if(L->size=0) printf("线性表为空，不能进行删除操作！ "); exit(1); L->size-; returnL->listL->size;/*返回原来表尾元素的值*/*15.从线性表L中删除第pos个元素并返回它，若删除失败则

12、停止程序运行*/elemTypedeletePosList(structList*L,intpos) elemTypetemp; inti; if(pos<1|pos>L->size)/*pos越界则删除失败*/ printf("pos值越界，不能进行删除操作！ "); exit(1); temp=L->listpos-1; for(i=pos;i<L->size;i+) L->listi-1=L->listi; L->size-; returntemp;/*16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返

13、回0*/intdeleteValueList(structList*L,elemTypex) inti,j; /*从线性表中顺序查找出值为x的第一个元素*/ for(i=0;i<L->size;i+) if(L->listi=x) break; /*若查找失败，表明不存在值为x的元素，返回0*/ if(i=L->size) return0; /*删除值为x的元素L->listi*/ for(j=i+1;j<L->size;j+) L->listj-1=L->listj; L->size-; return1;/*/voidmain()

14、inta10=2,4,6,8,10,12,14,16,18,20; inti; structListL; initList(&L,5); for(i=0;i<10;i+) insertLastList(&L,ai); insertPosList(&L,11,48);insertPosList(&L,1,64); printf("%d ",getElem(&L,1); traverseList(&L); printf("%d ",findList(&L,10); updatePosList(&a

15、mp;L,3,20); printf("%d ",getElem(&L,3); traverseList(&L); deleteFirstList(&L);deleteFirstList(&L); deleteLastList(&L);deleteLastList(&L); deletePosList(&L,5);deletePosList(&L,7); printf("%d ",sizeList(&L); printf("%d ",emptyList(&

16、L); traverseList(&L); clearList(&L); return0;#include<stdio.h>#include<stdlib.h>#defineNN12#defineMM20typedefintelemType;/*/*以下是关于线性表链接存储（单链表）操作的16种算法*/*/structsNode/*定义单链表结点类型*/ elemTypedata; structsNode*next;/*1.初始化线性表，即置单链表的表头指针为空*/voidinitList(structsNode*hl) *hl=NULL; return

17、;/*2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/voidclearList(structsNode*hl) /*cp和np分别作为指向两个相邻结点的指针*/ structsNode*cp,*np; cp=*hl; /*遍历单链表，依次释放每个结点*/ while(cp!=NULL) np=cp->next;/*保存下一个结点的指针*/ free(cp); cp=np; *hl=NULL;/*置单链表的表头指针为空*/ return;/*3.返回单链表的长度*/intsizeList(structsNode*hl) intcount=0;/*用于统计结点

18、的个数*/ while(hl!=NULL) count+; hl=hl->next; returncount;/*4.检查单链表是否为空，若为空则返回，否则返回*/intemptyList(structsNode*hl) if(hl=NULL) return1; else return0; /*5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/elemTypegetElem(structsNode*hl,intpos) inti=0;/*统计已遍历的结点个数*/ if(pos<1) printf("pos值非法，退出运行！ "); ex

19、it(1); while(hl!=NULL) i+; if(i=pos) break; hl=hl->next; if(hl!=NULL) returnhl->data; else printf("pos值非法，退出运行！ "); exit(1); /*6.遍历一个单链表*/voidtraverseList(structsNode*hl) while(hl!=NULL) printf("%5d",hl->data); hl=hl->next; printf(" "); return;/*7.从单链表中查找具有给

20、定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL*/elemType*findList(structsNode*hl,elemTypex) while(hl!=NULL) if(hl->data=x) return&hl->data; else hl=hl->next; returnNULL;/*8.把单链表中第pos个结点的值修改为x的值，若修改成功返回，否则返回*/intupdatePosList(structsNode*hl,intpos,elemTypex) inti=0; structsNode*p=hl; while(p!=

21、NULL)/*查找第pos个结点*/ i+; if(pos=i) break; else p=p->next; if(pos=i) p->data=x; return1; else return0; /*9.向单链表的表头插入一个元素*/voidinsertFirstList(structsNode*hl,elemTypex) structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("内存分配失败，退出运行！ "); exit(1); newP->data=x;/*把x

22、的值赋给新结点的data域*/ /*把新结点作为新的表头结点插入*/ newP->next=*hl; *hl=newP; return;/*10.向单链表的末尾添加一个元素*/voidinsertLastList(structsNode*hl,elemTypex) structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("内在分配失败，退出运行！ "); exit(1); /*把x的值赋给新结点的data域，把空值赋给新结点的next域*/ newP->data=x; new

23、P->next=NULL; /*若原表为空，则作为表头结点插入*/ if(*hl=NULL) *hl=newP; /*查找到表尾结点并完成插入*/ else structsNode*p=NULL; while(p->next!=NULL) p=p->next; p->next=newP; return;/*11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回，否则返回*/intinsetPosList(structsNode*hl,intpos,elemTypex) inti=0; structsNode*newP; structsNode*cp=*hl

24、,*ap=NULL; /*对pos值小于等于的情况进行处理*/ if(pos<=0) printf("pos值非法，返回表示插入失败！ "); return0; /*查找第pos个结点*/ while(cp!=NULL) i+; if(pos=i) break; else ap=cp; cp=cp->next; /*产生新结点，若分配失败，则停止插入*/ newP=malloc(sizeof(structsNode); if(newP=NULL) printf("内存分配失败，无法进行插入操作！ "); return0; /*把x的值赋给新结

25、点的data域*/ newP->data=x; /*把新结点插入到表头*/ if(ap=NULL) newP->next=cp;/*或改为newP->next=*hl;*/ *hl=newP; /*把新结点插入到ap和cp之间*/ else newP->next=cp; ap->next=newP; return1;/*插入成功返回1*/*12.向有序单链表中插入元素x结点，使得插入后仍然有序*/voidinsertOrderList(structsNode*hl,elemTypex) /*把单链表的表头指针赋给cp，把ap置空*/ structsNode*cp=

26、*hl,*ap=NULL; /*建立新结点*/ structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("内在分配失败，退出运行！ "); exit(1); newP->data=x;/*把x的值赋给新结点的data域*/ /*把新结点插入到表头*/ if(cp=NULL)|(x<cp->data) newP->next=cp; *hl=newP; return; /*顺序查找出x结点的插入位置*/ while(cp!=NULL) if(x<cp->d

27、ata) break; else ap=cp; cp=cp->next; /*把x结点插入到ap和cp之间*/ newP->next=cp; ap->next=newP; return;/*13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/elemTypedeleteFirstList(structsNode*hl) elemTypetemp; structsNode*p=*hl;/*暂存表头结点指针，以便回收*/ if(*hl=NULL) printf("单链表为空，无表头可进行删除，退出运行！ "); exit(1); *h

28、l=(*hl)->next;/*使表头指针指向第二个结点*/ temp=p->data;/*暂存原表头元素，以便返回*/ free(p);/*回收被删除的表头结点*/ returntemp;/*返回第一个结点的值*/*14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/elemTypedeleteLastList(structsNode*hl) elemTypetemp; /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/ structsNode*cp=*hl; structsNode*ap=NULL; /*单链表为空则停止运行*/ if(cp=NULL

29、) printf("单链表为空，无表头进行删除，退出运行！ "); exit(1); /*从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点*/ while(cp->next!=NULL) ap=cp; cp=cp->next; /*若单链表中只有一个结点，则需要修改表头指针*/ if(ap=NULL) *hl=(*hl)->next;/*或改为*hl=NULL;*/ /*删除表尾结点*/ else ap->next=NULL; /*暂存表尾元素，以便返回*/ temp=cp->data; free(cp);/*回收被删除的

30、表尾结点*/ returntemp;/*返回表尾结点的值*/*15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/elemTypedeletePosList(structsNode*hl,intpos) inti=0; elemTypetemp; /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/ structsNode*cp=*hl; structsNode*ap=NULL; /*单链表为空或pos值非法则停止运行 （编程入门）*/ if(cp=NULL)|(pos<=0) printf("单链表为空或pos值不正确，退出运行！ "

31、); exit(1); /*从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点*/ while(cp!=NULL) i+; if(i=pos) break; ap=cp; cp=cp->next; /*单链表中没有第pos个结点*/ if(cp=NULL) printf("pos值不正确，退出运行！ "); exit(1); /*若pos等于1，则需要删除表头结点*/ if(pos=1) *hl=(*hl)->next;/*或改为*hl=cp->next;*/ /*否则删除非表头结点，此时cp指向该结点，ap指向前驱结点*/ else ap->next=cp->next; /*暂存第pos个结点的值，以便返回*/ temp=cp->data; free(cp);/*回收被删除的第pos个结点*/ returntemp;/*返回在temp中暂存的第pos个结点的值*/*16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0*/intdeleteValueList(structsNode*hl,elemTypex) /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/ structsN