线性表习题
一、数据准备
#define ERROR0
#define TRUE1
#define FALSE0
#define OK1
#define MAXSIZE20/* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemTypedata;
structNode*next;
}Node;
typedefstructNode* LinkList;
二、初始化单向链表
Status InitList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
if(*L==NULL) {
returnERROR;
}
(*L)->next=NULL;
returnOK;
}
三、插入数据到单向链表
Status InsertList(LinkList *L,int index,ElemType data){
if(index<1) {
returnERROR;
}
if(*L==NULL) {
InitList(L);
}
LinkListp = *L;
inti=1;
while(i
p = p->next;
i++;
}
if(p ==NULL&& i==index) {
returnERROR;
}
//生成新结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data= data;
temp->next= p->next;
p->next= temp;
returnOK;
}
四、遍历单向链表
void TraverseList(LinkList L){
if(L ==NULL) {
return;
}
LinkListp = L->next;
while(p!=NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
五、作业
1.题目:
将2个递增的有序链表合并为一个有序链表; 要求结果链表仍然使用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据
void MergeList(LinkList *la,LinkList *lb,LinkList *lc){
//目标:将2个递增的有序链表La,Lb 合并为一个递增的有序链表Lc
if(*la==NULL&& lb ==NULL) {
return;
}else{
if(*la ==NULL) {
*lc = *lb;
}else{
*lc = *la;
}
}
//pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;
*lc = *la;
LinkListpa = (*la)->next;
LinkListpb = (*lb)->next;
LinkListpc = (*lc);
LinkListtemp;
while(pa && pb) {
if(pa->data< pb->data) {
//取较小者La中的元素,将pa链接在pc的后面,pa指针后移
pc->next= pa;
pc = pa;
pa = pa->next;
}elseif(pa->data> pb->data){
//取较小者Lb的元素,将pb链接在pc后面, pb指针后移
pc->next= pb;
pc = pb;
pb = pb->next;
}else{
//相等时取La中的元素,删除Lb的元素;
pc->next= pa;
pc = pa;
pa = pa->next;
temp = pb->next;
free(pb);
pb = temp;
}
}
//将非空表的剩余元素之间链接在Lc表的最后
pc->next= pa?pa:pb;
//释放Lb的头结点
free(*lb);
}
2.作业2:
题目:
已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中;
例如:
La = {2,4,6,8}; Lb = {4,6,8,10};
Lc = {4,6,8}
void Intersection(LinkList *la,LinkList *lb,LinkList *lc){
//目标: 求2个递增的有序链表La,Lb的交集, 使用头指针Lc指向带回;
*lc = *la;
LinkListpa,pb,pc,temp;
//用pa,pb指向la,lb中的数据，进行比较
pa = (*la)->next;
pb = (*lb)->next;
pc = *lc;
while(pa && pb) {
if(pa->data== pb->data) {
//相等取pa,删除pb
pc->next= pa;
pc = pa;
pa = pa->next;
temp = pb->next;
free(pb);
pb = temp;
}elseif(pa->data> pb->data){
//删除较小的pb
temp = pb;
pb = pb->next;
free(temp);
}else{
//删除较小的pa
temp = pa->next;
free(pa);
pa = temp;
}
}
//删除后面没比较过的数据
while(pa) {
temp = pa;
pa = pa->next;
free(temp);
}
while(pb) {
temp = pb;
pb = pb->next;
free(temp);
}
//
pc->next=NULL;
free(*lb);
}
3.作业3:
题目:
设计一个算法,将链表中所有节点的链接方向"原地旋转",即要求仅仅利用原表的存储空间. 换句话说,要求算法空间复杂度为O(1);
例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};
//后插法
void Inverse(LinkList *L){
LinkListp = (*L)->next;
(*L)->next=NULL;
LinkList q;
while(p !=NULL) {
q = p->next;
p->next= (*L)->next;
(*L)->next= p;
p = q;
}
}
4.作业4:
题目:
设计一个算法,删除递增有序链表中值大于等于mink且小于等于maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素;
解法一：
voidDeleteMinMax(LinkList*L,intmink,intmaxk){
LinkListp = (*L)->next;
LinkListq = (*L);
LinkListtemp;
while(p) {
if(p->data>mink && p->data< maxk) {
temp = p;
p = p->next;
q->next= p;
free(temp);
}else{
q = p;
p = p->next;
}
}
}
解法二：
//解法二：
voidDeleteMinMax2(LinkList*L,intmink,intmaxk){
//目标: 删除递增有序链表L中值大于等于mink 和小于等于maxk的所有元素
LinkListp,q,pre;
pre = *L;
LinkListtemp;
//p指向首元结点
p = (*L)->next;
//1.查找第一值大于mink的结点
while(p && p->data< mink) {
//指向前驱结点
pre = p;
p = p->next;
}
//2.查找第一个值大于等于maxk的结点
while(p && p->data<=maxk) {
p = p->next;
}
//3.修改待删除的结点指针
q = pre->next;
pre->next= p;
while(q != p) {
temp = q->next;
free(q);
q = temp;
}
}
5.题目5:
设将n(n>1)个整数存放到一维数组R中, 试设计一个在时间和空间两方面都尽可能高效的算法;将R中保存的序列循环左移p个位置(0
例如: pre[10] = {0,1,2,3,4,5,6,7,8,9},
n = 10,p = 3;
pre[10] = {3,4,5,6,7,8,9,0,1,2}
//交换元素
voidReverse(int*pre,intleft,intright){
inti = left;
intj = right;
while(i
pre[i] = pre[i] + pre[j];
pre[j] = pre[i] - pre[j];
pre[i] = pre[i] - pre[j];
i++;
j--;
}
}
//n为数组长度，p为移动几位，p<n
voidLeftShift(int*pre,intn,intp){
//将长度为n的数组pre 中的数据循环左移p个位置
if(p>0&& p
//1. 将数组中所有元素全部逆置
Reverse(pre,0, n-1);
//2. 将前n-p个数据逆置
Reverse(pre,0, n-1-p);
//3. 将后p个数据逆置
Reverse(pre, n-p, n-1);
}
}
6.题目6:
已知一个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.
int MainElement(int *A,int n){
//目标: 求整数序列A中的主元素;
//count 用来计数
intcount =1;
//key 用来保存候选主元素, 初始A[0]
intkey = A[0];
//1,3,5,2,5,5,5
//(1) 扫描数组,选取候选主元素
for(inti=1; i
if(A[i] == key) {
//(2) 如果A[i]元素值 == key ,则候选主元素计数加1;
count++;
}else{
if(count>0) {
//(3) 当前元素A[i] 非候选主元素,计数减1;
count--;
}else{
//(4) 如果count 等于0,则更换候选主元素,重新计数
key = A[i];
count =1;
}
}
}
//如果count >0
if(count>0) {
//(5)统计候选主元素的实际出现次数
for(inti=0; i
if(A[i] == key) {
count++;
}
}
}
//(6)判断count>n/2, 确认key是不是主元素
if(count>n/2) {
returnkey;
}
//不存在主元素
return-1;
}
7.题目7:
用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};
void DeleteEqualNode(LinkList *L,int n){
//目标: 删除单链表中绝对值相等的结点;
//1. 开辟辅助数组p.
int*p =alloca(sizeof(int)*n);
// int *p = malloc(sizeof(int)*n);
//2.数组元素初始值置空
for(inti=0; i
*(p+i) =0;
}
//3.指针temp 指向首元结点
//4.遍历链表,直到temp = NULL;
LinkListtemp = (*L)->next;
LinkListr = *L;
while(temp !=NULL) {
//5.如果该绝对值已经在结点上出现过,则删除该结点
if(p[abs(temp->data)] ==1) {
//移除
//临时指针指向temp->next
r->next= temp->next;
//删除temp指向的结点
free(temp);
//temp 指向删除结点下一个结点
temp = r->next;
}else{
//6. 未出现过的结点,则将数组中对应位置置为1;
p[abs(temp->data)] =1;//记录已经出现过了
r = temp;
//继续向后遍历结点
temp = temp->next;
}
}
}
六、验证
intmain(intargc,constchar* argv[]) {
printf("线性表练习篇!\n");
//链表相关的题目,有兴趣的可以尝试:https://leetcode-cn.com/tag/linked-list/
StatusiStatus;
LinkListLa,Lb,Lc,L;
InitList(&La);
InitList(&Lb);
//// ---------作业1--------
// printf("******题目1:********\n");
// //设计2个递增链表La,Lb
// for(int j = 10;j>=0;j-=2)
// {
// iStatus = InsertList(&La, 1, j);
// }
// printf("La:\n");
// TraverseList(La);
//
// for(int j = 11;j>0;j-=2)
// {
// iStatus = InsertList(&Lb, 1, j);
// }
// printf("Lb:\n");
// TraverseList(Lb);
//
// MergeList(&La, &Lb, &Lc);
// printf("Lc:\n");
// TraverseList(Lc);
// /*---------作业2--------*/
// printf("******题目2:********\n");
// InsertList(&La, 1, 8);
// InsertList(&La, 1, 6);
// InsertList(&La, 1, 4);
// InsertList(&La, 1, 2);
// printf("La:\n");
// TraverseList(La);
//
//
// InsertList(&Lb, 1, 10);
// InsertList(&Lb, 1, 8);
// InsertList(&Lb, 1, 6);
// InsertList(&Lb, 1, 4);
// printf("Lb:\n");
// TraverseList(Lb);
//
// Intersection(&La, &Lb, &Lc);
// printf("Lc:\n");
// TraverseList(Lc);
// /*---------作业3--------*/
// printf("******题目3:********\n");
// InitList(&L);
// for(int j = 10;j>=0;j-=2)
// {
// iStatus = InsertList(&L, 1, j);
// }
// printf("L逆转前:\n");
// TraverseList(L);
//
// Inverse(&L);
// printf("L逆转后:\n");
// TraverseList(L);
// /*---------作业4--------*/
// printf("******题目4:********\n");
// InitList(&L);
// for(int j = 10;j>=0;j-=2)
// {
// iStatus = InsertList(&L, 1, j);
// }
// printf("L链表:\n");
// TraverseList(L);
//
// DeleteMinMax(&L, 4, 10);
// printf("删除链表mink与maxk之间结点的链表:\n");
// TraverseList(L);
// /*---------作业5--------*/
// printf("******题目5:********\n");
// int pre[10] = {0,1,2,3,4,5,6,7,8,9};
// LeftShift(pre, 10, 3);
// for (int i=0; i < 10; i++) {
// printf("%d ",pre[i]);
// }
// printf("\n");
// // /*---------作业6--------*/
// printf("******题目6:********\n");
// int A[] = {0,5,5,3,5,7,5,5};
// int B[] = {0,5,5,3,5,1,5,7};
// int C[] = {0,1,2,3,4,5,6,7};
//
// int value = MainElement(A, 8);
// printf("数组A 主元素为: %d\n",value);
// value = MainElement(B, 8);
// printf("数组B 主元素为(-1表示数组没有主元素): %d\n",value);
// value = MainElement(C, 8);
// printf("数组C 主元素为(-1表示数组没有主元素): %d\n",value);
/*---------作业7--------*/
//21,-15,15,-7,15
printf("******题目7:********\n");
InitList(&L);
InsertList(&L,1,21);
InsertList(&L,1, -15);
InsertList(&L,1,15);
InsertList(&L,1, -7);
InsertList(&L,1,15);
DeleteEqualNode(&L,21);
TraverseList(L);
return0;
}
