【数据结构周周练】001顺序表与链表（含上海大学832计算机组成原理与数据结构原题）

本文主要是介绍【数据结构周周练】001顺序表与链表（含上海大学832计算机组成原理与数据结构原题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

一、练习1：删除顺序表指定部分元素

1、题目

2、代码

3、运行结果

二、练习2：逆置链表

1、题目

2、代码

3、运行结果

三、练习3：拆分链表

1、题目

2、代码

3、运行结果

前言

从这周开始，我会不定期发一些数据结构练习题，一方面，提升自己的编程能力，给自己考研代码题打基础，虽然逻辑都明白，但是一次性写对代码还是有问题，思维不细致；另一方面，给想学习数据结构的同学提供一些编程的练习题，希望能对大家有所帮助。题目代码方式不唯一，欢迎大家提供新的解题思路或代码。

一、练习1：删除顺序表指定部分元素

1、题目

从给定顺序表中删除i~j的所有元素（包括i，j）。以顺序表：0123456789为例，i取3，j取6。

2、代码

#define MAXLISTSIZE 20
#define LISTINCREMENT 5
#define OVERFLOW -1#include<iostream>
#include<malloc.h>using namespace std;typedef int ElemType;
typedef struct{ElemType *elem;int length;int listSize;
}SqList;int InitSqList(SqList &S) {S.elem = (ElemType *)malloc(MAXLISTSIZE * sizeof(SqList));if (!S.elem){return OVERFLOW;}S.length = 0;S.listSize = MAXLISTSIZE;
}int CreatSqList(SqList &S) {for (int i = 0; i <= 9; i++){if (S.length>S.listSize){ElemType * newBase = (ElemType *)realloc(S.elem, (S.listSize + LISTINCREMENT) * sizeof(ElemType));//重新分配基地址S.elem = newBase;if (!S.elem){return OVERFLOW;}}S.length++;S.elem[i] = i;}return 1;
}int DeleteElem(SqList &S) {for (int i = 7; i <= S.length; i++){S.elem[i-4] = S.elem[i];}S.length -= 4;return 1;
}void VisitSqList(SqList S) {for (int i = 0; i < S.length; i++){cout << S.elem[i] << ",";}cout << endl;
}
void main() {SqList S;InitSqList(S);CreatSqList(S);cout << "原顺序表为：" << endl;VisitSqList(S);DeleteElem(S);cout << "删除元素后顺序表为：" << endl;VisitSqList(S);
}

3、运行结果

二、练习2：逆置链表

1、题目

创建一个长度为10的线性单链表：0123456789。并将其逆置，要求逆置过程不能创立新结点。

2、代码

#include<iostream>
#include<malloc.h>
using namespace std;typedef int ElemType;//建立链表
typedef struct LNode
{ElemType elem;struct LNode *next;
}LNode,*LinkList;//初始化链表
int InitList(LinkList &L) {L = (LinkList)malloc(sizeof(LNode));if (!L)//存储分配失败exit(OVERFLOW);L->next = NULL;return 1;
}//尾插法创建链表
int CreatList(LinkList &L) {L->elem = 0;LinkList p = L;LinkList q;for (int i = 1; i <= 9; i++){q = (LinkList)malloc(sizeof(LNode));q->elem = i;q->next = NULL;p->next = q;p = q;q = p->next;}return 1;
}//头插法逆置链表
int HeadInsertList(LinkList &L) {LinkList p,q;p = L->next;q = p;L->next = NULL;while (q){q = p->next;p->next = L;L = p;p = q;}return 1;
}//遍历链表，查看逆置结果。
void VisitList(LinkList L) {LinkList p = L;while (p){cout << p->elem << ",";p = p->next;}cout << endl;
}
void main() {LinkList L;InitList(L);CreatList(L);cout << "遍历L：" << endl;VisitList(L);HeadInsertList(L);cout << "遍历逆序后的L" << endl;VisitList(L);
}

3、运行结果

三、练习3：拆分链表

1、题目

将一个长度为10的线性单链表：0123456789中的偶数取出，放到另一个单链表中，要求保持原来顺序。

2、代码

#include<iostream>
#include<malloc.h>
using namespace std;typedef int ElemType;//建立链表
typedef struct LNode
{ElemType elem;struct LNode *next;
}LNode, *LinkList;//初始化链表
int InitList(LinkList &L) {L = (LinkList)malloc(sizeof(LNode));if (!L)//存储分配失败exit(OVERFLOW);L->next = NULL;return 1;
}//尾插法创建链表
int CreatList(LinkList &L) {LinkList p = L;LinkList q;for (int i = 0; i <= 9; i++){q = (LinkList)malloc(sizeof(LNode));q->elem = i;q->next = NULL;p->next = q;p = q;q = p->next;}return 1;
}
//分解链表
int ApartList(LinkList &L, LinkList &M) {LinkList p = L;LinkList q = L->next;LinkList m = M;while (q){if (q->elem % 2 == 0){p->next = q->next;p = q->next;m->next = q;			q->next = NULL;m = q;}q = p->next;}return 1;
}void VisitList(LinkList &L) {LinkList p = L->next;while (p){cout << p->elem << ",";p = p->next;}cout << endl;
}void main() {LinkList L, M;InitList(L);CreatList(L);cout << "分解前的L链表为：";VisitList(L);InitList(M);ApartList(L, M);cout << "分解后的L链表为：";VisitList(L);cout << "分解后的M链表为：";VisitList(M);
}