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

落日映苍穹つ 2021-06-11 15:12 392阅读 0赞

**目录**

前言

一、练习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、运行结果 ##

![70][]

# 二、练习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、运行结果 ##

![70 1][]

# 三、练习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);
    }

## 3、运行结果 ##

![70 2][]

[70]: /images/20210516/9b1b564fd32a42388cdf10b7e16cf483.png
[70 1]: /images/20210516/961e2711ce7e43c58ae24ae9320eea01.png
[70 2]: /images/20210516/c87445d2ac7e4c45bc68d922674f6825.png