【数据结构周周练】001顺序表与链表
目录
前言
从这周开始,我会不定期发一些数据结构练习题,一方面,提升自己的编程能力,给自己考研代码题打基础,虽然逻辑都明白,但是一次性写对代码还是有问题,思维不细致;另一方面,给想学习数据结构的同学提供一些编程的练习题,希望能对大家有所帮助。题目代码方式不唯一,欢迎大家提供新的解题思路或代码。
一、练习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);
}