C语言手撕数据结构代码_顺序表_静态存储_动态存储

顺序表例题

题目清单:

顺序表基于静态存储习题
1.创建一个顺序表
2.从顺序表中删除第i个元素
3.在第i个元素前插入e
4.从顺序表中删除最小元素，空出的位置由最后一个元素填补
5.在无序顺序表中删除值在s和t之间的所有元素
6.在非递减顺序表中删除值在区间[s,t]的所有元素
7.删除非递减顺序表中的重复元素

顺序表基于动态存储习题
8.顺序表A和B的元素个数分别为m和n，表A升序，表B降序排序，两个表中都不在相同的元素
8.1 将两表合并，两表中的元素存储到表C中(c表保持升序)
8.2 表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排序
9.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解交集
10.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解A-B（差集）
11.设计算法算法逆置顺序表
12.将序列L循环左移动

1.创建一个顺序表

// 本程序为顺序表模版
#include <iostream>
#define MAX_SIZE 100 //确定顺序表总的空间大小为100
typedef int ElemType;
typedef struct sqlist
{ElemType list[MAX_SIZE];int length; //记录表长
}sqlist;void print_list(sqlist a)
{for (int i=0; i<a.length; i++) {printf("%d->",a.list[i]);}
}
int main() {sqlist a;a.length=0; //初始化单链表表长为7for(int i=0;i<=6;i++){a.list[i]=i+1;a.length++;}     //定义一个 1，2，3，4，5，6，7的顺序表printf("检查顺序表的第一个元素：%d\n当前顺序表的表长为：%d\n",a.list[0],a.length);printf("--------打印读入链表-----------\n");print_list(a);printf("\n");printf("-----------------------------\n");return 1;
}

2.从顺序表中删除第i个元素

void delete_i(sqlist &a,int x)
{for(int i=x;i<a.length;i++){a.list[i-1]=a.list[i];}a.list[a.length-1]=0;//清空最后一个值的数据a.length--;
}

3.在第i个元素前插入e

void insert_i(sqlist &a,int x,int e)
{for(int i=a.length;i>=x;i--){a.list[i]=a.list[i-1];}a.list[x-1]=e;a.length++;
}

4.从顺序表中删除最小元素，空出的位置由最后一个元素填补

void delete_min(sqlist &a)
{int min=100000;int flag=0;for(int i=0;i<a.length;i++){if(a.list[i]<min){min=a.list[i];flag=i;}}a.list[flag]=a.list[a.length-1];a.length--;
}

5.在无序顺序表中删除值在s和t之间的所有元素

void deleteElem(sqlist &a,int s,int t)
{int curlength=0;//指向表头的指针，同时也记录着新表的长度for(int i=0;i<a.length;i++){if(a.list[i]<s||a.list[i]>t){a.list[curlength++]=a.list[i];}}a.length=curlength;
}

6.在非递减顺序表中删除值在区间[s,t]的所有元素

从前后找到第一个s，从后往前找到最后一个t，将t后面加入到第一个s前面

//在无序顺序表中删除s和t之间的所有元素
void delete_st(sqlist &a,int s,int t)
{int first_s=0;int last_t=0;int curlength1=0; //记录s前新表长度int curlength2=0; //记录t后新表长度for(int i=0;i<a.length;i++){if(a.list[i]>=s){first_s=i;break;}else curlength1++;}for(int j=a.length-1;j>=0;j--){if(a.list[j]<=t){last_t=j;break;}else curlength2++;}for(int i=first_s,j=last_t+1;j<a.length;j++,i++){a.list[i]=a.list[j];}a.length=curlength1+curlength2;printf("length=%d\n",a.length);
}

7.删除非递减顺序表中的重复元素

思想:新表表尾和旧表元素不同时，加入新表

void delete_repeat(sqlist &a)
{int curlength=0;for(int i=1;i<a.length;i++){if(a.list[curlength]!=a.list[i]){a.list[++curlength]=a.list[i];}}a.length=curlength+1; //长度=下标+1
}

---

从第8题开始，存储方式改为动态存储

---

8.顺序表A和B的元素个数分别为m和n，表A升序，表B降序排序，两个表中都不在相同的元素

关于动态存储顺序表

typedef int ElemType;
typedef struct SqList
{ElemType *PList;int length;int listSize;
}SqList;

8.1 将两表合并，两表中的元素存储到表C中(c表保持升序)

void combine(sqList &a,sqlist &b,sqlist &c)
{c.length=a.length+b.length;c.list=(ElemType *)malloc(sizeof(ElemType)*c.length);int curlength=0;int index_a=0; //指向a第一个元素的指针int index_b=b.length-1; //指向b最后一个元素的指针while(index_a<a.length&&index_b>=0){if(a.list[index_a]<b.list[index_b]){//把a加入cc.list[curlength++]=a.list[index_a];index_a++;}else{//把b加入cc.list[curlength++]=b.list[index_b];index_b--;}}//把a或b中的剩余元素加入c中while(index_a<a.length){c.list[curlength++]=a.list[index_a];index_a++;}while(index_b>=0){c.list[curlength++]=b.list[index_b];index_b--;}
}

8.2 表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排序

一直以最后一个元素为目标，依次的插入进前面的递增序列。不断更新最后一个元素。

void combine_a(sqList &a ,int k)
{for(int i=0;i<a.length-1;i++){if(a.list[a.length-1]<=a.list[i]){int temp=a.list[a.length-1];for(int j=a.length-1;j>i;j--)//包括i在内的所有元素后移{a.list[j]=a.list[j-1];}a.list[i]=temp;}}
}

9.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解交集

解析:

分别设置两个指针指向两个集合开头，若集合A开头元素小于B集合开头元素，则说明B集合的其他元素都大于A，故A后移一位，反之B后移一位，每当相等的时候，加入交集，同时A和B同时后移一位，直到其中一个表为空时，退出循环。在a表中存储交集

设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出：应为 5 7 9
代码如下:

void jiaoji(sqList &a,sqlist &b)
{int curlength=0;int index_a=0;int index_b=0;while (index_a<a.length||index_b<b.length) {if(a.list[index_a]<b.list[index_b]){index_a++;}else if(a.list[index_a]==b.list[index_b]){a.list[curlength++]=a.list[index_a];index_a++;index_b++;}else{index_b++;}}a.length=curlength;
}

10.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解A-B（差集）

解析:

每次将A小于的元素加入进差集当中
设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出：应为 1 2 15
代码如下:

void chaji(sqList &a,sqlist &b)
{int curlength=0;int index_a=0;int index_b=0;while (index_a<a.length||index_b<b.length) {if(a.list[index_a]<b.list[index_b]){a.list[curlength++]=a.list[index_a++];}else if(a.list[index_a]==b.list[index_b]){index_a++;index_b++;}else{index_b++;}}while (index_a<a.length) { //如果b短，将a中剩余的元素加入a.list[curlength++]=a.list[index_a++];}a.length=curlength;}

11.设计算法算法逆置顺序表

void reverse(sqList &a)
{int low=0;int high=a.length-1;while (low<high) {int temp=a.list[low];a.list[low++]=a.list[high];a.list[high--]=temp;}
}

12.将序列L循环左移动

解析:使用三次逆置

void r_reverse(sqList &a,int low,int high)
{while (low<high) {int temp=a.list[low];a.list[low++]=a.list[high];a.list[high--]=temp;}
}
void ROL(sqList &a,int r)
{r_reverse(a,0,r-1);r_reverse(a,r,a.length-1);r_reverse(a, 0,a.length-1);
}