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 奇偶分配

/*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 删除最大节点

/*删除最大节点*/
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 逆序

/*双链表节点逆置算法*/
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 循环链表

待续