02第二章、线性表

第二章、线性表

2.2.2 顺序表：

算法库：

01 头文件+定义

#include <iostream>
#include <string.h>
#include <map>
#include<queue>
#include<unordered_map>
using namespace std;
#pragma warning(disable:4996)

#define MaxSize 50
typedef int ElemType;

typedef struct {
	ElemType data[MaxSize];//元素
	int length;//长度
}SqList;

02 建立与初始化

/*建立顺序表*/
void CreateList(SqList*& L, ElemType a[], int n) {
	int i = 0, k = 0;//k表示元素个数
	L = (SqList*)malloc(sizeof(SqList));
	while (i < n) {
		L->data[i] = a[i];
		k++; i++;
	}
	L->length = k;
}

void InitList(SqList*& L) {
	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0;
}

03 销毁、判空、长度、打印

/*销毁线性表*/
void DestroyList(SqList*& L) {
	free(L);
}

/*是否为空*/
bool ListEmpty(SqList* L) {
	return (L->length == 0);
}

/*返回长度*/
int ListLength(SqList* L) {
	return (L->length);
}

/*打印线性表*/
void DispList(SqList* L) {
	for (int i = 0; i < L->length; i++)
		printf("%d ", L->data[i]);
	printf("\n");
}

04 得到第 i 的元素

/*得到第i的元素*/
bool GetElem(SqList* L, int i, ElemType& e) {
	if (i<1 || i>L->length)
		return false;
	e = L->data[i - 1];
	return true;
}

05 返回元素 e 的下标

/*返回元素e的下标*/
int LocateElem(SqList* L, ElemType e) {
	int i = 0;
	while (i < L->length&& L->data[i] != e)
		i++;
	if (i >= L->length)return 0;
	else return i + 1;
}

06 在第 i 个位置插入元素

/*在第i个位置插入元素*/
bool ListInsert(SqList*& L, int i, ElemType e) {
	int j;
	if (i<1 || i>L->length + 1)return false;
	i--;
	for (j = L->length; j > i; j--)
		L->data[j] = L->data[j - 1];
	L->data[i] = e;
	L->length++;
	return true;
}

07 删除第 i 个元素

/*删除第i个元素*/
bool ListDelete(SqList*& L, int i, ElemType e) {
	int j;
	if (i<1 || i>L->length)return false;
	i--;
	e = L->data[i];
	for (j = i; j < L->length - 1; j++)L->data[j] = L->data[j + 1];
	L->length--;
	return true;
}

所有

#include <iostream>
#include <string.h>
#include <map>
#include<queue>
#include<unordered_map>
using namespace std;
#pragma warning(disable:4996)

#define MaxSize 50
typedef int ElemType;

typedef struct {
	ElemType data[MaxSize];//元素
	int length;//长度
}SqList;

/*建立顺序表*/
void CreateList(SqList*& L, ElemType a[], int n) {
	int i = 0, k = 0;//k表示元素个数
	L = (SqList*)malloc(sizeof(SqList));
	while (i < n) {
		L->data[i] = a[i];
		k++; i++;
	}
	L->length = k;
}

void InitList(SqList*& L) {
	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0;
}

/*销毁线性表*/
void DestroyList(SqList*& L) {
	free(L);
}

/*是否为空*/
bool ListEmpty(SqList* L) {
	return (L->length == 0);
}
/*返回长度*/
int ListLength(SqList* L) {
	return (L->length);
}
/*打印线性表*/
void DispList(SqList* L) {
	for (int i = 0; i < L->length; i++)
		printf("%d ", L->data[i]);
	printf("\n");

}
/*得到第i的元素*/
bool GetElem(SqList* L, int i, ElemType& e) {
	if (i<1 || i>L->length)
		return false;
	e = L->data[i - 1];
	return true;
}

/*返回元素e的下标*/
int LocateElem(SqList* L, ElemType e) {
	int i = 0;
	while (i < L->length&& L->data[i] != e)
		i++;
	if (i >= L->length)return 0;
	else return i + 1;
}

/*在第i个位置插入元素*/
bool ListInsert(SqList*& L, int i, ElemType e) {
	int j;
	if (i<1 || i>L->length + 1)return false;
	i--;
	for (j = L->length; j > i; j--)
		L->data[j] = L->data[j - 1];
	L->data[i] = e;
	L->length++;
	return true;
}

/*删除第i个元素*/
bool ListDelete(SqList*& L, int i, ElemType e) {
	int j;
	if (i<1 || i>L->length)return false;
	i--;
	e = L->data[i];
	for (j = i; j < L->length - 1; j++)L->data[j] = L->data[j + 1];
	L->length--;
	return true;
}

int main() {
	SqList* sqlist;
	int a[3] = { 1,2,3 };

	InitList(sqlist);
	CreateList(sqlist, a, 3);

	DispList(sqlist);

}

2.3.2 单链表

算法库

#include <iostream>
#include <string.h>
#include <map>
#include<queue>
#include<unordered_map>
using namespace std;
#pragma warning(disable:4996)

#define MaxSize 50
typedef int ElemType;

typedef struct LNode{
	ElemType data;//元素
	struct LNode* next;
}LinkNode;

/*头插法*/
void CreateListF(LinkNode *&L,ElemType a[],int n) {
	LinkNode* s;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;//建立头节点，将next域置为null
	for (int i = 0; i < n;i++) {//循环建立数据节点s
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];//数据存入
		s->next = L->next;//将节点s的next是L的next，sn->ln
		L->next = s;//节点L的nest是s，ln->s
	}
}

/*尾插法*/
void CreateListR(LinkNode*& L, ElemType a[], int n) {
	LinkNode* s,*r;
	L = (LinkNode*)malloc(sizeof(LinkNode));//创建头节点
	r = L;//r始终指向尾节点，初始是指向头节点
	for (int i = 0; i < n; i++) {//循环建立数据节点
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];//存入
		r->next = s;//将节点s插入到节点r之后,r指向尾节点
		r = s;//尾巴后面插元素，然后尾巴移到后一个元素，保证r始终是尾巴
	}
	r->next = NULL;//为节点的next置为null
}

/*初始化线性表*/
void InitList(LinkNode *&L) {
	L = (LinkNode *)malloc(sizeof(LinkNode));
	L->next = NULL;//指向null
}

/*销毁线性表*/
void DestroyList(LinkNode*&L) {
	LinkNode* pre = L, * p = L->next;
	while(p!=NULL){
		free(pre);//销毁节点，从头结点开始
		pre = p;
		p = pre->next;
	}
	free(pre);
}

/*判断是否是空*/
bool ListEmpty(LinkNode *L) {
	return L->next == NULL;
}

/*求长度*/
int ListLength(LinkNode *L) {
	int n = 0;
	LinkNode* p = L;
	while (p->next!=NULL) {
		n++;
		p = p->next;
	}
	return n;
}

/*打印单链表*/
void DispList(LinkNode* L) {
	LinkNode* p = L->next;
	while (p!= NULL) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

/*求第i个位置的元素值*/
bool GetElem(LinkNode *L,int i,ElemType &e) {
	int j = 0;
	LinkNode* p = L;
	if (i <= 0) return false;
	while (j < i && p != NULL) {//移动到位置i
		j++;
		p = p->next;
	}
	if (p == NULL)return false;
	else {
		e = p->data;//得到
		return true;
	}
}

/*按元素值查找，得到下标*/
int LocateElem(LinkNode *L,ElemType e) {
	int i = 1;
	LinkNode* p = L->next;
	while (p!=NULL && p->data!=e) {//移到对应元素值
		p = p->next;
		i++;
	}
	if (p == NULL)return 0;
	else return i;

}

/*在第i个位置插入元素e*/
bool ListInsert(LinkNode *&L,int i,ElemType e) {
	int j = 0;
	LinkNode* p = L, * s;
	if (i <= 0)return false;
	while (j <i-1 && p!=NULL) {
		j++;
		p = p->next;
	}
	if (p==NULL)
		return false;
	else {
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = e;
		s->next = p->next;//头插法
		p->next = s;
		return true;
	}
}

/*删除单链表下标i的元素，并返回*/
bool ListDelete(LinkNode*& L, int i, ElemType e) {
	int j = 0;
	LinkNode* p = L, * q;
	if (i <= 0)return false;
	while (j < i - 1 && p != NULL) {
		j++;//移动指针
		p = p->next;
	}
	if (p == NULL)
		return false;
	else {
		q = p->next;
		if (q == NULL)return false;
		e = q->data;
		p->next = q->next;//p->next=p->next->next;
		free(q);
		return true;
	}
}

例题 2.6 奇偶分配

[例2.6]有一个带头结点的单链表L=(a1,b1,a2,b2,…,an,bn)，设计一个算法将其拆分成两个带头结点的单链表L1和L2，其中L1=(a1,a2,…,an),L2=(bn,b(n-1),…,b1),要求L1使用L的头结点。
解：利用原单链表L中的所有结点通过改变指针域重组成两个单链表L1和L2。由于L1中结点的相对顺序与L中的相同，所以采用尾插法建立单链表L1；由于L2中结点的相对顺序与L中的相反，所以采用头插法建立单链表L2。算法如下：

/*L1顺序奇数，L2逆序偶数*/
void split(LinkNode *&L,LinkNode *&L1,LinkNode *&L2) {
	LinkNode* p = L->next, * q, * r1;//p指向第一个数据节点
	L1 = L;//L1利用原来L的头节点
	r1 = L1;//r1指向L1尾节点
	L2 = (LinkNode*)malloc(sizeof(LinkNode));//创建L2
	L2->next = NULL;//null
	while (p!=NULL) {
		r1->next = p;  //尾插法将*p（ai）插入L1中
		r1 = p;
		p = p->next;  //下移动
		q = p->next;  //因为头插法会修改指针域，所以用q保存p的后继节点
		p->next = L2->next;//p插在L2前面
		L2->next = p;
		p = q;   //p重新指向ai+1的节点
	}
	r1->next = NULL;  //尾巴节点置空
}

例题 2.7 删除最大节点

[例2.7]设计一个算法，删除一个单链表L中元素值最大的结点（假设这样的结点唯一）

解：在单链表中删除一个结点先要找到它的前驱结点，用指针p扫描整个单链表，pre指向结点的前驱结点，在扫描时用maxp指向data域值最大的结点，maxpre指向maxp所指结点的前驱结点。当单链表扫描完毕后，通过maxpre所指结点删除其后的结点，即删除了结点值最大的结点。
算法如下：

/*删除最大节点*/
void delmaxnode(LinkNode *&L) {
	LinkNode* p = L->next, * pre = L, * maxp = p,*maxpre = pre;
	while (p!=NULL) {//用p扫描整个单链表，pre始终指向其前驱节点
		if (maxp->data<p->data) {//若找到一个更大的节点
			maxp = p;//更新maxp;
			maxpre = pre;//更新maxpre
		}
		pre = p;//p,pre同步后移一个节点
		p = p->next;
	}
	maxpre->next = maxp->next;//删除
	free(maxp);//释放
}

例题 2.8 排序

void sort(LinkNode *&L) {
	LinkNode* p, * pre, * q;
	p = L->next->next;//p指向L的第二个数据节点
	L->next->next = NULL;//构造只含一个数据节点的有序单链表
	while (p!=NULL){
		q = p->next;//q保存p节点后继结点的指针
		pre = L;    //从有序单链表开头进行比较，pre指向插入节点的前驱节点
		while (pre->next!=NULL && pre->next->data<p->data) {
			pre = pre->next;//在有序单链表中找插入p所指节点的前驱节点（pre所指向）
		}
		p->next = pre->next;//在pre所指结点之后插入p所指节点
		pre->next = p;
		p = q;  //扫描原单链表余下的节点
	}
}

例题 2.9 简单选择排序

LinkNode* getMin(LinkNode*& L) {
	LinkNode* min = L, * head = L;
	while (head->next) {
		if (min->data > (head->next->data))
			min = head->next;
		head = head->next;
	}
	return min;
}

void SortList(LinkNode*& L) {
	LinkNode* j, * i = L->next;
	int temp;
	for (; i->next != NULL; i = i->next) {
		j = getMin(i);
		if (i->data != j->data) {
			temp = i->data;
			i->data = j->data;
			j->data = temp;
		}
	}
}

int main() {
	LinkNode* linknode;
	InitList(linknode);
	ElemType a[10] = { 1,6,2,9,4,7,5,2,0,2 };
	CreateListR(linknode, a, 10);

	printf("原链表:\n");
	DispList(linknode);

	SortList(linknode);
	printf("排序后链表:\n");
	DispList(linknode);

	system("pause");
}

例题 2.9 不带头结点

版本 2：不带头结点

void sort(linklist *L){
	 linkNode * p,*pre,*max,*maxpre;
	 linlist *h=L;
	 L=NULL;
	 while(h!=NULL){				//持续扫描原链表
	 	p=max=h;pre=maxpre=NULL;
	    while(p!=NULL){
	    	if(p->data>max->data){  //找到更大的，记忆它和它的前驱
			   max=p;
			   maxpre=pre;
	     	}
			 pre=p;					//继续寻找
			 p=p->next;
		}
		if(s==h)					//最大结点在原链表前段
		   h=h->next;
		else
		   maxpre->next=max->next;//最大结点在原链表内
		   max->next=L;//头插
		   L=max;
	 }
}

例题 2.3.2.1 交换前后节点

题目描述：线性表中各结点的检索概率不等,则可用如下策略提高顺序检索的效率:

若找到指定的结点,将该结点和其前驱结点)交换,

使得经常被检索的结点尽量位于表的前端,

试设计一个算法在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

LinkNode* LinkSearch(LinkNode* L, ElemType e) {
	if (L == NULL)return NULL;
	LinkNode* p=L;
	while (p->next!=NULL && p->next->data!=e)
	{
		p = p->next;
	}
	if (p->next!=NULL) {
		printf("\n查找成功\n");
		if (p!=L) {
			ElemType t = p->data;
			p->data = p->next->data;
			p->next->data = t;
			return p;
		}
		return p->next;
	}
	else {
		printf("\n查找失败！\n");
		return NULL ;
	}
	return NULL;
}

2.3.3 双链表

算法库：

#include <iostream>
#include <string.h>
#include <map>
#include<queue>
#include<unordered_map>
using namespace std;
#pragma warning(disable:4996)

#define MaxSize 50
typedef int ElemType;

typedef struct DNode{
	ElemType data;//元素
	struct DNode* prior;  //前驱节点
	struct DNode* next;   //后继节点
}DLinkNode;

/*头插法*/
void CreateListF(DLinkNode*&L,ElemType a[],int n) {
	DLinkNode* s;
	L = (DLinkNode*)malloc(sizeof(DLinkNode));
	L->prior = L->next = NULL;//前后指针域置为null
	for (int i = 0; i < n;i++) {//循环建立数据节点s
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = a[i];//数据存入
		s->next = L->next;//将节点s插入到原首节点之前、头节点之后
		if (L->next!=NULL) {//若L存在数据节点，修改L->next的前驱指针
			L->next->prior = s;
		}
		L->next = s;
		s->prior = L;
	}
}

/*尾插法*/
void CreateListR(DLinkNode*& L, ElemType a[], int n) {
	DLinkNode* s,*r;
	L = (DLinkNode*)malloc(sizeof(DLinkNode));//创建头节点
	r = L;//r始终指向尾节点，初始是指向头节点
	for (int i = 0; i < n; i++) {//循环建立数据节点
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = a[i];//存入
		r->next = s;//将节点s插入到节点r之后,r指向尾节点
		s->prior = r;
		r = s;//尾巴后面插元素，然后尾巴移到后一个元素，保证r始终是尾巴
	}
	r->next = NULL;//为节点的next置为null
}

/*在第i个位置插入元素e*/
bool ListInsert(DLinkNode*& L, int i, ElemType e) {
	int j = 0;
	DLinkNode* p = L, * s;  //p指向头节点，j设置为0
	if (i <= 0)return false; //i错误返回false
	while (j < i - 1 && p != NULL) {//查找第i-1个节点
		j++;
		p = p->next;
	}
	if (p == NULL)//未找到第i-1个节点
		return false;
	else {
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = e;
		s->next = p->next;//头插法，在p节点之后插入s
		if (p->next != NULL) //若p节点存在后继节点，修改其前驱指针
			p->next->prior = s;
		s->prior = p;
		p->next = s;
		return true;
	}
}

/*删除双链表下标i的元素，并返回*/
bool ListDelete(DLinkNode*& L, int i, ElemType e) {
	int j = 0;
	DLinkNode* p = L, * q;
	if (i <= 0)return false;
	while (j < i - 1 && p != NULL) {
		j++;//移动指针
		p = p->next;
	}
	if (p == NULL)
		return false;
	else {
		q = p->next;
		if (q == NULL)return false;
		e = q->data;
		p->next = q->next;//p->next=p->next->next;
		if (p->next != NULL)p->next->prior = p;
		free(q);
		return true;
	}
}



/*初始化线性表*/
void InitList(DLinkNode*&L) {
	L = (DLinkNode*)malloc(sizeof(DLinkNode));
	L->next = NULL;//指向null
}

/*销毁线性表*/
void DestroyList(DLinkNode*&L) {
	DLinkNode* pre = L, * p = L->next;
	while(p!=NULL){
		free(pre);//销毁节点，从头结点开始
		pre = p;
		p = pre->next;
	}
	free(pre);
}

/*判断是否是空*/
bool ListEmpty(DLinkNode*L) {
	return L->next == NULL;
}

/*求长度*/
int ListLength(DLinkNode*L) {
	int n = 0;
	DLinkNode* p = L;
	while (p->next!=NULL) {
		n++;
		p = p->next;
	}
	return n;
}

/*打印单链表*/
void DispList(DLinkNode* L) {
	DLinkNode* p = L->next;
	while (p!= NULL) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

/*求第i个位置的元素值*/
bool GetElem(DLinkNode*L,int i,ElemType &e) {
	int j = 0;
	DLinkNode* p = L;
	if (i <= 0) return false;
	while (j < i && p != NULL) {//移动到位置i
		j++;
		p = p->next;
	}
	if (p == NULL)return false;
	else {
		e = p->data;//得到
		return true;
	}
}

/*按元素值查找，得到下标*/
int LocateElem(DLinkNode*L,ElemType e) {
	int i = 1;
	DLinkNode* p = L->next;
	while (p!=NULL && p->data!=e) {//移到对应元素值
		p = p->next;
		i++;
	}
	if (p == NULL)return 0;
	else return i;
}

例题 2.9 逆序

[例2.9]有一个带头结点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素……最后一个元素变为第1个元素。
解：先构造只有一个头结点的空双链表L（利用原来的头结点），用p扫描双链表的所有数据结点，采用头插法将所指结点插人到L中。
算法如下：

/*双链表节点逆置算法*/
void reverse(DLinkNode *&L) {
	DLinkNode* p = L->next, * q;//p指向首节点
	L->next = NULL;       //构造只有头节点的双链表L
	while (p!=NULL) {	//扫描所有节点
		q = p->next;   //会修改p节点的next域，用q临时保存其后继节点
		p->next = L->next;  //头插法将p插入双链表中
		if (L->next != NULL)//若L中存在数据节点
			L->next->prior = p;//修改原来首节点的前驱指针
		L->next = p;//将新节点作为首节点
		p->prior = L;
		p = q;//让p中心指向其后继节点

	}
}

例题 2.10 排序

与 2.8 基本相同

/*排序*/
void sort(DLinkNode*& L) {
	DLinkNode* p, * pre, * q;
	p = L->next->next;//p指向L的第二个数据节点
	L->next->next = NULL;//构造只含一个数据节点的有序双链表
	while (p != NULL) {
		q = p->next;//q保存p节点后继结点的指针
		pre = L;    //从有序双链表开头进行比较，pre指向插入节点的前驱节点
		while (pre->next != NULL && pre->next->data < p->data)
			pre = pre->next;//在有序双链表中找插入p所指节点的前驱节点（pre所指向）
		p->next = pre->next;//在pre所指结点之后插入p所指节点
		if (pre->next != NULL)
			pre->next->prior = p;
		pre->next = p;
		p->prior = pre;
		p = q;  //扫描原双链表余下的节点
	}
}

2.3.4 循环链表

待续