设为首页加入收藏夹
数据结构C语言实现之线性表
全国计算机应用水平考试   2009-09-23 11:42:59 作者:SystemMaster 来源: 文字大小:[][][]

#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){  /*分配失败则退出运行*/
     printf("存储空间分配失败! ");
     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->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.返回线性表L当前的长度,若L为空则返回0*/
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("元素序号越界! ");
     exit(1);
   }
   returnL->list[pos-1];  /*返回线性表中序号为pos值的元素值*/
}
/*6.顺序扫描(即遍历)输出线性表L中的每个元素*/
voidtraverseList(structList*L)
{
   inti;
   for(i=0;i<L->size;i++){
     printf("%d",L->list[i]);
   }
   printf(" ");
   return;
}
/*7.从线性表L中查找值与x相等的元素,若查找成功则返回其位置,否则返回-1*/
intfindList(structList*L,elemTypex)
{
   inti;
   for(i=0;i<L->size;i++){
     if(L->list[i]==x){
       returni;
     }
   }
   return-1;
}
/*8.把线性表L中第pos个元素的值修改为x的值,若修改成功返回1,否则返回0*/
intupdatePosList(structList*L,intpos,elemTypex)
{
   if(pos<1||pos>L->size){  /*若pos越界则修改失败*/
     return0;
   }
   L->list[pos-1]=x;
   return1;
}
/*9.向线性表L的表头插入元素x*/
voidinserFirstList(structList*L,elemTypex)
{
   inti;
   if(L->size==L->maxSize){
     againMalloc(L);
   }
   for(i=L->size-1;i>=0;i--){
     L->list[i+1]=L->list[i];
   }
   L->list[0]=x;
   L->size++;
   return;
}
/*10.向线性表L的表尾插入元素x*/
voidinsertLastList(structList*L,elemTypex)
{
   if(L->size==L->maxSize){  /*重新分配更大的存储空间*/
     againMalloc(L);
   }
   L->list[L->size]=x;  /*把x插入到表尾*/
   L->size++;  /*线性表的长度增加1*/
   return;
}
/*11.向线性表L中第pos个元素位置插入元素x,若插入成功返回1,否则返回0*/
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->list[i+1]=L->list[i];
   }
   L->list[pos-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->list[i]){
       break;
     }
   }
   /*从表尾到下标i元素依次后移一个位置,把i的位置空出来*/
   for(j=L->size-1;j>=i;j--)
     L->list[j+1]=L->list[j];
   /*把x值赋给下标为i的元素*/  
   L->list[i]=x;
   /*线性表长度增加1*/
   L->size++;
   return;
}
/*13.从线性表L中删除表头元素并返回它,若删除失败则停止程序运行*/
elemTypedeleteFirstList(structList*L)
{
   elemTypetemp;
   inti;
   if(L->size==0){
     printf("线性表为空,不能进行删除操作! ");
     exit(1);
   }
   temp=L->list[0];
   for(i=1;i<L->size;i++)
     L->list[i-1]=L->list[i];
   L->size--;
   returntemp;
}
/*14.从线性表L中删除表尾元素并返回它,若删除失败则停止程序运行*/
elemTypedeleteLastList(structList*L)
{
   if(L->size==0){
     printf("线性表为空,不能进行删除操作! ");
     exit(1);
   }
   L->size--;
   returnL->list[L->size];    /*返回原来表尾元素的值*/
}
/*15.从线性表L中删除第pos个元素并返回它,若删除失败则停止程序运行*/
elemTypedeletePosList(structList*L,intpos)
{
   elemTypetemp;
   inti;
   if(pos<1||pos>L->size){    /*pos越界则删除失败*/
     printf("pos值越界,不能进行删除操作! ");
     exit(1);
   }
   temp=L->list[pos-1];
   for(i=pos;i<L->size;i++)
     L->list[i-1]=L->list[i];
   L->size--;
   returntemp;
}
/*16.从线性表L中删除值为x的第一个元素,若成功返回1,失败返回0*/
intdeleteValueList(structList*L,elemTypex)
{
   inti,j;
   /*从线性表中顺序查找出值为x的第一个元素*/
   for(i=0;i<L->size;i++){
     if(L->list[i]==x){  
       break;
     }
   }
   /*若查找失败,表明不存在值为x的元素,返回0*/
   if(i==L->size){
     return0;
   }
   /*删除值为x的元素L->list[i]*/
   for(j=i+1;j<L->size;j++){
     L->list[j-1]=L->list[j];
   }
   L->size--;
   return1;
}
/************************************************************************/
voidmain()
{
   inta[10]={2,4,6,8,10,12,14,16,18,20};
   inti;
   structListL;
   initList(&L,5);
   for(i=0;i<10;i++){
     insertLastList(&L,a[i]);
   }
   insertPosList(&L,11,48);    insertPosList(&L,1,64);
   printf("%d ",getElem(&L,1));
   traverseList(&L);
   printf("%d ",findList(&L,10));
   updatePosList(&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(&L));
   traverseList(&L);
  
clearList(&L);
   return0;
}#include<stdio.h>
#include<stdlib.h>
#defineNN12
#defineMM20
typedefintelemType;
/************************************************************************/
/*      以下是关于线性表链接存储(单链表)操作的16种算法    */
/************************************************************************/
structsNode{  /*定义单链表结点类型*/
   elemTypedata;
   structsNode*next;
};
/*1.初始化线性表,即置单链表的表头指针为空*/
voidinitList(structsNode**hl)
{
   *hl=NULL;
   return;
}
/*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;    /*用于统计结点的个数*/
   while(hl!=NULL){
     count++;
     hl=hl->next;
   }
   returncount;
}
/*4.检查单链表是否为空,若为空则返回1,否则返回0*/
intemptyList(structsNode*hl)
{
   if(hl==NULL){
     return1;
   }else{
     return0;
   }
}
/*5.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行*/
elemTypegetElem(structsNode*hl,intpos)
{
   inti=0;    /*统计已遍历的结点个数*/
   if(pos<1){
     printf("pos值非法,退出运行! ");
     exit(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.从单链表中查找具有给定值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的值,若修改成功返回1,否则返回0*/
intupdatePosList(structsNode*hl,intpos,elemTypex)
{
   inti=0;
   structsNode*p=hl;
   while(p!=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的值赋给新结点的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;
   newP->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的结点,若插入成功返回1,否则返回0*/
intinsetPosList(structsNode**hl,intpos,elemTypex){
   inti=0;
   structsNode*newP;
   structsNode*cp=*hl,*ap=NULL;
   /*对pos值小于等于0的情况进行处理*/
   if(pos<=0){
     printf("pos值非法,返回0表示插入失败! ");
     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的值赋给新结点的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=*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->data){
       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);
   }
   *hl=(*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){
     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);    /*回收被删除的表尾结点*/
   returntemp;    /*返回表尾结点的值*/
}
/*15.从单链表中删除第pos个结点并返回它的值,若删除失败则停止程序运行*/
elemTypedeletePosList(structsNode**hl,intpos)
{
   inti=0;
   elemTypetemp;
   /*初始化cp和ap指针,使cp指向表头结点,使ap为空*/
   structsNode*cp=*hl;
   structsNode*ap=NULL;
   /*单链表为空或pos值非法则停止运行
http://bianceng.cn(编程入门)*/
   if((cp==NULL)||(pos<=0)){
     printf("单链表为空或pos值不正确,退出运行! ");
     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为空*/
   structsNode*cp=*hl;
   structsNode*ap=NULL;
   /*从单链表中查找值为x的结点,找到后由cp指向该结点,由ap指向其前驱结点*/
   while(cp!=NULL){
     if(cp->data==x){
       break;
     }
     ap=cp;
     cp=cp->next;
   }
   /*若查找失败,即该单链表中不存在值为x的结点,则返回0*/
   if(cp==NULL){
     return0;
   }
   /*如果删除的是表头或非表头结点则分别进行处理*/
   if(ap==NULL){
     *hl=(*hl)->next;    /*或改为*hl=cp->next*/
   }else{
     ap->next=cp->next;
   }
   free(cp);    /*回收被删除的结点*/
   return1;    /*返回1表示删除成功*/
}
/************************************************************************/
intmain(intargc,char*argv[])
{
   inta[NN];
   inti;
   structsNode*p,*h,*s;
   srand(time(NULL));
   initList(&p);
   for(i=0;i<NN;i++){
     a[i]=rand()&MM;
   }
   printf("随机数序列:");
   for(i=0;i<NN;i++){
     printf("%5d",a[i]);
   }
   printf(" ");
   printf("随机数逆序:");
   for(i=0;i<NN;i++){
     insertFirstList(&p,a[i]);
   }
   traverseList(p);
   printf("单链表长度:%5d ",sizeList(p));
   for(h=p;h!=NULL;h=h->next){
     while(deleteValueList(&(h->next),h->data)){
       ;
     }
   }
   printf("去除重复数:");
   traverseList(p);
   printf("单链表长度:%5d ",sizeList(p));
   h=NULL;
   for(s=p;s!=NULL;s=s->next){
     insertOrderList(&h,s->data);
   }
   printf("有序表序列:");
   traverseList(h);
   clearList(&p);
   system("pause");
   return0;
}


Copyright 2007-2024 www.nitedu.org.cn 京ICP备09086538号-1