顺序表的定义、初始化、创建、打印、按值查找、插入(时间复杂度为O(n))、删除(时间复杂度为O(n))、销毁、合并两个顺序表
#include <stdio.h>#include <stdlib.h> //malloc函数会用到此头文件#define MAX 30;//顺序表元素个数最大为30//函数声明void initlist(Sqlist* L); //初始化顺序表void createlist(Sqlist* L); //创建顺序表void printlist(Sqlist* L); //打印顺序表void insertlist(Sqlist* L, int pos, Elemtype e); //插入操作void deletlist(Sqlist* L, int pos, Elemtype e); //删除操作typedef int Elemtype; //将Elemtype定义为int类型//顺序表的定义typedef struct{Elemtype* elem; //顺序表的元素int length; //顺序表的长度}Sqlist; //将Sqlist定义为结构体类型，里面定义了顺序表元素和顺序表的长度两个成员//初始化顺序表void initlist(Sqlist* L){L->elem = (Elemtype*)malloc(sizeof(Elemtype)*MAX);//sizeof(Elemtype)算每个元素大小再*MAX就是整个顺序表的大小，(Elemtype *)表示开辟空间来存什么类型的数L->length = 0; //将顺序表的长度设为0，因为是空表}//总结初始化顺序表：//1.给顺序表分配空间//2.将表长设为0//用户输入数据创建顺序表void createlist(Sqlist* L){int i,n;printf("请输入存放的元素个数：");scanf("%d",&n);printf("请输入一组数字存到顺序表中：");for(i = 0;i < n; i++){scanf("%d",&L->elem[i]); //将输入直接存放到顺序表中L->length++; //每放一个元素，表长+1}}//总结创建顺序表：//1.用户输入顺序表的元素个数//2.用户依次输入顺序表的元素，存入顺序表中//3.表长+1//打印顺序表void printlist(Sqlist* L){int i;for(i = 0; i < L->length; i++){printf("%d ",L->elem[i]);}}//按值查找void searchlist(Sqlist* L, Elemtype e){int i;for(i = 0; i < L->length; i++){if(L->elem[i] == e){printf("找到了，下标是%d", i);}}}
插入元素：
//插入元素void insertlist(Sqlist* L, int pos, Elemtype e)//在第pos位置插入元素e，pos是元素的下标{int len = L->length; //将表长(也就是元素个数)用变量len表示，方便后续书写int i;if((pos>=0) && (pos < len)) //判断插入位置是否合法，必须插入存放着有元素的下标的位置 {if(len < MAX) //判断顺序表元素个数是否已满最大值，已经满了就不能插入元素了{for(i = len-1; i >= pos; i--){L->elem[i+1] = L->elem[i] //将前一个元素放入后一个下标位置中}L->elem[pos] = e; //将要插入的元素插入第pos位置L->length++; //增加元素后，表长+1}}}//总结插入元素：//1.判断插入位置是否合法//2.判断表是否已占满//3.从最后一个元素开始，每次将一个元素向后移动一个位置(其本质是复制元素的值)//4.将新元素插入指定位置//5.表长+1
删除元素：
//删除元素void deletlist(Sqlist* L, int pos, Elemtype e){int len = L->length;int i;if((pos >= 0) && (pos < len)){for(i = pos+1; i < len; i++){//将后一个元素放入前一个下标位置中L->elem[i-1] = L->elem[i]; //这句第一次写的时候错了，记住是第i个赋值给i-1个}L->length--; //删除元素后，表长-1}}//总结删除元素：//1.判断删除位置是否合法//2.从删除指定元素的位置+1开始，将后面的元素每次向前移动一个位置(其本质是复制元素的值)//3.表长-1
销毁顺序表：
//销毁顺序表void destorylist(Sqlist* L){if(L->elem) //顺序表中存在元素才能销毁{free(L->elem); //将空间释放L->elem = NULL; //释放后一定要置为空指针}L->length = 0; //表长设为0}
合并两个顺序表：
新表中可以有重复的数字
依次取出表A中的一个元素和表B的一个元素比较，哪个元素值小，则将这个元素放到表C的表尾
//将A、B表合并为新表Cvoid Union(Sqlist A, Sqlist B, Sqlist& C){//新表C的表长就是A表+B表的表长C.length = A.length + B.length;//给表C分配内存空间C.elem = (int*)malloc(C.length);//pa、pb、pc分别指向对应的表的第一个元素int* pa = A.elem;int* pb = B.elem;int* pc = C.elem;//lasta、lastb分别指向对应的表的最后一个元素int* lasta = A.elem + (A.length - 1);int* lastb = B.elem + (B.length - 1);//判断是否到了表尾，到了表尾退出循环while (pa <= lasta && pb <= lastb){//A表的元素小于B表的元素，就将A表的元素插入新表里if (*pa < *pb){//将A表的元素赋值给新表*pc = *pa;//pa指向下一个元素pa++;//pc指向下一个元素pc++;//增加元素后，C表长+1C.length++;}else{//将B表的元素赋值给新表*pc = *pb;//pb指向下一个元素pb++;//pc指向下一个元素pc++;//增加元素后，C表长+1C.length++;}}//A表到了表尾，就将B表剩余元素给C表if (pa = lasta){while (pb <= lastb){//将B表的元素赋值给新表*pc = *pb;//pb指向下一个元素pb++;//pc指向下一个元素pc++;//增加元素后，C表长+1C.length++;}}//B表到了表尾，就将A表剩余元素给C表else{while (pa <= lasta){//将A表的元素赋值给新表*pc = *pa;//pa指向下一个元素pa++;//pc指向下一个元素pc++;//增加元素后，C表长+1C.length++;}}}
