代码实现
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
//线性表元素数据类型
#define ElemType int
//线性表初始长度
#define InitSize 100
//线性表
typedef struct {
//数据元素
ElemType *data;
//线性表名称（最高10个字符）
char name[10];
//线性表当前长度和最大长度
int length, MaxSize;
} SeqList;
//存放线性表的线性表
typedef struct {
//线性表元素
SeqList *list;
//当前线性表的个数，线性表最大长度
int length, MaxSize;
} ListOfLists;
//函数声明
int GetList(ListOfLists AllList, char name[]);
//初始化线性表(创建线性表)
void InitList(SeqList *list, char name[]) {
//给线性表数据元素分配内存空间
list->data = (ElemType *) malloc(InitSize * sizeof(ElemType));
strcpy(list->name, name);
list->length = 0;
list->MaxSize = InitSize;
}
//线性表扩容
bool MultipleList(SeqList *list) {
if (list->data != NULL) {
//扩容至原来的两倍
list->data = (ElemType *) realloc(list->data, list->MaxSize * sizeof(ElemType) * 2);
list->MaxSize = list->MaxSize * 2;
return true;
}
// printf("扩容失败，线性表已被销毁！\n");
return false;
}
//初始化存放线性表的线性表
void InitListOfLists(ListOfLists *list) {
list->list = (SeqList *) malloc(InitSize * sizeof(SeqList));
list->length = 0;
list->MaxSize = InitSize;
}
//扩容存放线性表的线性表
bool MultipleListOfLists(ListOfLists *list) {
//因为总线性表不会被销毁，所以直接扩容即可,无需再判断是否为销毁的线性表
list->list = (SeqList *) realloc(list->list, list->MaxSize * sizeof(SeqList) * 2);
//判断扩容是否成功
if (list->list != NULL) {
list->MaxSize = list->MaxSize * 2;
return true;
}
return false;
}
//添加线性表插入到存放线性表的线性表中
void AddList(ListOfLists *AllList, SeqList list) {
if (AllList->length == AllList->MaxSize) {
//如果总线性表满了，就对总线性表进行扩容
MultipleListOfLists(AllList);
}
AllList->list[AllList->length] = list;
AllList->length++;
}
//给线性表添加数据元素
void AddElem(ListOfLists *AllList, SeqList *list, ElemType Elem) {
//如果线性表已满，就先进行扩容
if (list->length == list->MaxSize) {
MultipleList(list);
}
list->data[list->length] = Elem;
list->length++;
//将总线性表里的这个线性表进行更新
AllList->list[GetList(*AllList, list->name)] = *list;
}
//查找某个指定名称的线性表
SeqList FindList(ListOfLists AllList, char name[]) {
for (int i = 0; i < AllList.length; i++) {
if (strcmp(AllList.list[i].name, name) == 0) {
return AllList.list[i];
}
}
SeqList empty;
empty.data = NULL;
strcpy(empty.name, "");
empty.length = 0;
empty.MaxSize = 0;
return empty;
}
//根据线性表名称返回在总线性表中的数组下标
int GetList(ListOfLists AllList, char name[]) {
for (int i = 0; i < AllList.length; i++) {
if (strcmp(AllList.list[i].name, name) == 0) {
return i;
}
}
return -1;
}
//打印所有线性表
void PrintAllList(ListOfLists AllList) {
if (AllList.length == 0) {
printf("当前线性表为空！\n");
return;
}
for (int i = 0; i < AllList.length; i++) {
printf("%d -> %s\n", i, AllList.list[i].name);
}
}
//打印线性表的数据元素
void PrintList(SeqList list) {
if (list.length == 0) {
printf("当前线性表为空！\n");
return;
}
for (int i = 0; i < list.length; i++) {
printf("%d -> %d\n", i, list.data[i]);
}
}
/*-----------------------------以上是线性表基础操作，下面是王道课后习题代码-----------------------------------------*/
//P17线性表02题;设计一个高效算法，将顺序表L中的所有元素逆置，要求算法的空间复杂度为o(1)
//采用指针的思想，设计头尾两个指针，通过交换指针所指元素来完成逆置操作。由于没有借助额外的辅助数组，所以空间复杂度为o(1)。
void Reverse(ListOfLists *AllList, SeqList *list) {
//定义左右指针
int left = 0, right = list->length - 1;
//定义临时变量，用于数据交换
ElemType temp;
for (; left < right; left++, right--) {
temp = list->data[left];
list->data[left] = list->data[right];
list->data[right] = temp;
}
//将逆置后的数组更新在总线性表中
AllList->list[GetList(*AllList, list->name)] = *list;
}
//P17线性表03题;对长度为n的顺序表L，编写一个时间复杂度为o(n),空间复杂度为o(1)的算法，该算法删除线性表中所有值为x的数据元素。
//空间复杂度为o(1)，说明不准使用辅助数组，但是可以使用辅助变量，辅助变量用多少个都行。时间复杂度为o(n),说明你只能扫一遍顺序表。
void Delete_x(ListOfLists *AllList, SeqList *list, ElemType x) {
//不等于x的元素个数
int k = 0;
//1 2 3 4 x 1 2 3 x 1 2 3 x
//k
//i
//1 2 3 4 x 1 2 3 x 1 2 3 x
// k
// i
//1 2 3 4 x 1 2 3 x 1 2 3 x
// k
// i
//1 2 3 4 x 1 2 3 x 1 2 3 x
// k
// i
//1 2 3 4 x 1 2 3 x 1 2 3 x
// k i
//1 2 3 4 1 1 2 3 x 1 2 3 x
// k i
//1 2 3 4 1 2 2 3 x 1 2 3 x
// k i
//1 2 3 4 1 2 3 3 x 1 2 3 x
// k i
//1 2 3 4 1 2 3 3 x 1 2 3 x
// k i
//1 2 3 4 1 2 3 1 x 1 2 3 x
// k i
//1 2 3 4 1 2 3 1 2 1 2 3 x
// k i
//1 2 3 4 1 2 3 1 2 3 2 3 x
// k i
for (int i = 0; i < list->length; i++) {
//当数据不是x时，k+1
if (x != list->data[i]) {
list->data[k] = list->data[i];
k++;
}
}
//将新的线性表长度设置为k
list->length = k;
//更新总线性表
AllList->list[GetList(*AllList, list->name)] = *list;
}
//P17线性表04题;从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
//为了这个题，先写个排序算法。就用冒泡排序吧。
void swap(ElemType *a, ElemType *b) {
ElemType temp;
temp = *a;
*a = *b;
*b = temp;
}
void BubbleSort(SeqList *list) {
for (int i = 0; i < list->length; i++) {
for (int j = 0; j < list->length - 1 - i; j++) {
if (list->data[j] > list->data[j + 1])
swap(&list->data[j], &list->data[j + 1]);
}
}
}
void Delete_s2t(ListOfLists *AllList, SeqList *list, ElemType s, ElemType t) {
if (s >= t) {
printf("S与T的值不合法！\n");
return;
} else if (list->length == 0) {
printf("顺序表为空！删除失败\n");
return;
}
//记录s的位置和s到t之间有多少个数据元素
int num = 0;
//先把list变成有序表(递增)
BubbleSort(list);
for (int i = 0; i < list->length; i++) {
if (!(list->data[i] >= s && list->data[i] <= t)) {
list->data[num] = list->data[i];
num++;
}
}
list->length = num;
//更新总线性表
AllList->list[GetList(*AllList, list->name)] = *list;
}
//P17线性表06题;从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
void Delete_Repeat(ListOfLists *AllList, SeqList *list) {
//先对线性表进行排序
BubbleSort(list);
//记录不重复元素的个数
int num = 0;
for (int i = 0; i < list->length - 1; i++) {
if (list->data[i] != list->data[i + 1]) {
list->data[num] = list->data[i];
num++;
}
}
list->data[num] = list->data[list->length - 1];
list->length = ++num;
PrintList(*list);
//更新总线性表
AllList->list[GetList(*AllList, list->name)] = *list;
}
//P17线性表07题;将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
//采用双指针对比的思想，分别给两个顺序表一个指针，进行对比。
SeqList MergeList(SeqList list1, SeqList list2, char name[]) {
SeqList merge;
InitList(&merge, name);
BubbleSort(&list1);
BubbleSort(&list2);
//定义两个指针
int index1 = 0, index2 = 0;
int i;
for (i = 0; index1 < list1.length && index2 < list2.length; i++) {
if (list1.data[index1] < list2.data[index2]) {
if (merge.length == merge.MaxSize) {
MultipleList(&merge);
}
merge.data[i] = list1.data[index1++];
} else {
if (merge.length == merge.MaxSize) {
MultipleList(&merge);
}
merge.data[i] = list2.data[index2++];
}
}
// if(index1>=list1.length){
// for(;index2<list2.length;index2++){
// if (merge.length == merge.MaxSize) {
// MultipleList(&merge);
// }
// merge.data[i++] = merge.data[index2];
// }
// merge.length = i;
// return merge;
// }
// else{
// for(;index1<list1.length;index1++){
// if (merge.length == merge.MaxSize) {
// MultipleList(&merge);
// }
// merge.data[i++] = merge.data[index1];
// }
// merge.length = i;
// return merge;
// }
//上面这种处理方式有错误，但我找不出来
while (index1 < list1.length) {
if (merge.length == merge.MaxSize) {
MultipleList(&merge);
}
merge.data[i++] = list1.data[index1++];
}
while (index2 < list2.length) {
if (merge.length == merge.MaxSize) {
MultipleList(&merge);
}
merge.data[i++] = list2.data[index2++];
}
merge.length = i;
return merge;
}
int main() {
//初始化总线性表
ListOfLists AllLists;
InitListOfLists(&AllLists);
//定义线性表
SeqList list, list1, list2;
//定义数据元素(s和t是题目中需要用到的变量)
ElemType Elem, s, t;
//定义线性表名称
char ListName[10], ListName1[10], ListName2[10];
//定义菜单选择变量和数组下标索引
int choice, index;
while (1) {
printf("\n菜单\n"
"1.创建线性表\n"
"2.查看当前所有线性表\n"
"3.指定线性表添加元素\n"
"4.查看指定线性表的所有数据元素\n"
"---------以下是王道题目操作-----------\n"
"5.逆置指定线性表\n"
"6.删除指定线性表中所有值为x的元素\n"
"7.删除指定有序线性表中s到t之间的所有元素\n"
"8.删除重复元素，使线性表每个元素数据唯一\n"
"9.指定两个有序顺序表，并将其合并为新的线性表\n"
"10.退出程序\n"
"请输入要进行的操作:");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入你要创建的线性表的名称(不超过10个字符):");
scanf("%s", ListName);
if (FindList(AllLists, ListName).data != NULL) {
printf("线性表已存在!\n");
break;
}
//创建新线性表
InitList(&list, ListName);
//将线性表添加到总线性表中
AddList(&AllLists, list);
break;
case 2:
PrintAllList(AllLists);
break;
case 3:
printf("请输入你要添加元素的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
list = FindList(AllLists, ListName);
printf("请输入你要添加的数据值:");
scanf("%d", &Elem);
AddElem(&AllLists, &list, Elem);
break;
case 4:
printf("请输入你要查看的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
list = FindList(AllLists, ListName);
PrintList(list);
break;
case 5:
printf("请输入你要逆置的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
list = FindList(AllLists, ListName);
Reverse(&AllLists, &list);
break;
case 6:
printf("请输入要删除元素的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
printf("请输入要删除的元素数值:");
scanf("%d", &Elem);
list = FindList(AllLists, ListName);
Delete_x(&AllLists, &list, Elem);
break;
case 7:
printf("请输入要删除元素的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
printf("请输入要删除的起始数值s:");
scanf("%d", &s);
printf("请输入要删除的终止数值t:");
scanf("%d", &t);
Delete_s2t(&AllLists, &list, s, t);
break;
case 8:
printf("请输入要删除元素的线性表的名称:");
scanf("%s", ListName);
if (GetList(AllLists, ListName) == -1) {
printf("找不到该线性表!\n");
break;
}
Delete_Repeat(&AllLists, &list);
break;
case 9:
printf("请输入要合并的第一个线性表的名称:");
scanf("%s", ListName1);
if (GetList(AllLists, ListName1) == -1) {
printf("找不到该线性表!\n");
break;
}
printf("请输入要合并的第二个线性表的名称:");
scanf("%s", ListName2);
if (GetList(AllLists, ListName2) == -1) {
printf("找不到该线性表!\n");
break;
}
printf("请输入合并后新线性表的名称:");
scanf("%s", ListName);
list = MergeList(FindList(AllLists, ListName1), FindList(AllLists, ListName2), ListName);
AddList(&AllLists, list);
break;
case 10:
exit(0);
default:
printf("输入的操作数有误，请重新输入！\n");
break;
}
}
}