前言
本文介绍线性表顺序存储时基本操作的实现，包括顺序表的结构定义、初始化、插入、删除、销毁、显示、清空、判空、求长度、查找，以及线性表的合并。
主要参考：严蔚敏“数据结构及应用算法教程”教材
代码如下
#include <stdio.h>
#include <stdlib.h>#define LIST_INIT_SIZE 100 //链表的初始容量
#define LISTINCREMENT 10 //扩容时的增量
#define OK 1
#define OVERFLOW -1
#define error 0typedef int ElemType;
typedef int Status;typedef struct //顺序表的结构定义
{ElemType *elem; //存储数据元素的一维数组int length; //线性表的当前长度int listsize; //当前分配的容量
}SqList;void InitList_sq(SqList *L) //初始化
{L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); //分配空间if(!L->elem) //判断分配是否成功exit(OVERFLOW);L->length=0; //初始化长度为0L->listsize=LIST_INIT_SIZE; //初始化容量为100
}Status ListInsert_sq(SqList *L,int i,ElemType x) //插入
{ElemType *newbase,*q,*p;if(i<1 || i>L->length+1) //判断插入位置的合理性return error;if(L->length >= L->listsize) //若顺序表的长度已经大于初始容量，则需要扩容{newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) //判断扩容是否成功exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT; //增加存储容量}q=&(L->elem[i-1]); //q记录插入地址for(p=L->elem + L->length-1;p>=q;p--)*(p+1)=*p; //插入位置及之后的元素右移*q=x; //插入元素xL->length++; //更新表长(表长加1)return OK;
}void ListDelete_Sq(SqList *L,int i) //删除
{ElemType *delete_i,*q,*e;if(i<1||i>L->length) //判断Loc的合理性printf("error!");delete_i=&(L->elem[i-1]); //指针p指向被删除元素的位置*e=L->elem[i-1]; //被删除的元素赋给eq=L->elem+L->length-1; //记录线性表的表尾地址for(delete_i++;delete_i<=q;delete_i++)*(delete_i-1)=*delete_i; //被删除元素之后的元素向左移动L->length--; //更新表长
}Status DestroyList(SqList *L) //销毁
{int i;for(i=0;i<L->length;i++){L->elem[i]=0;free(L->elem[i]); //释放内存空间}L->length=0; //清空长度L->listsize=0; //清空容量printf("销毁成功\n");return OK;
}void show_SqList(SqList *L) //显示
{int i;for(i=0;i<L->length;i++)printf("elem[%d]=%d\n",i+1,L->elem[i]);printf("\n");
}void clearList_Sq(SqList *L) //清空
{L->length=0;printf("清空成功\n");
}int listempty(SqList *L) //判空
{if(L->length==0)printf("为空\n");elseprintf("不为空\n");return 0;
}int ListLength_Sq(SqList *L) //求长度
{printf("%d\n",L->length);return L->length;
}int ListSearch_sq(SqList *L,int key) //查找
{int i=1;int *p=&(L->elem[0]);while(i<=L->length &&(*p!=key)){p++;i++;}if(i<L->length)return i;elsereturn 0;
}int MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc) //合并
{int *pa = &(La->elem[0]); //指针pa指向La表头的位置int *pb = &(Lb->elem[0]); //指针pb指向Lb表头的位置Lc->listsize = Lc->length = La->length+Lb->length; //初始化Lcint *pc = Lc->elem = (int *)malloc(Lc->listsize*sizeof(int)); //给Lc分配空间if(!Lc->elem){return -1; //存储分配失败}int *pa_last = &(La->elem[La->length-1]); //指针pa_last指向La表尾的位置int *pb_last = &(Lb->elem[Lb->length-1]); //指针pb_last指向Lb表尾的位置while(pa<=pa_last && pb<=pb_last){if(*pa<=*pb){*pc=*pa;pc++;pa++;}else{*pc=*pb;pc++;pb++;}}while(pa<=pa_last) //插入La的剩余元素{*pc=*pa;pc++;pa++;}while(pb<=pb_last) //插入Lb的剩余元素{*pc=*pb;pc++;pb++;}return 0;
}int main()
{int i;int key=5;SqList L;SqList La,Lb,Lc;InitList_sq(&L);InitList_sq(&La);InitList_sq(&Lb);for(i=0;i<10;i++)ListInsert_sq(&L,i+1,i+1);printf("原表顺序表:\n");show_SqList(&L);printf("插入后,在3位置插入7:\n");ListInsert_sq(&L,7,3);show_SqList(&L);printf("删除后,把3位置删除:\n");ListDelete_Sq(&L,3);show_SqList(&L);printf("顺序表的长度:\n");ListLength_Sq(&L);printf("判断顺序表是否为空:\n");listempty(&L);printf("查找元素:%d\n",key);printf("被查找元素的位序是:%d\n",ListSearch_sq(&L,key));clearList_Sq(&L);DestroyList(&L);for(i=0;i<10;i++)ListInsert_sq(&La,i+1,i+1);printf("顺序表La为:\n");show_SqList(&La);for(i=0;i<10;i++)ListInsert_sq(&Lb,i+1,i+8);printf("顺序表Lb为:\n");show_SqList(&Lb);MergeList_Sq(&La,&Lb,&Lc);printf("顺序表Lc为:\n");show_SqList(&Lc);return 0;
}
运行结果
