数据结构代码小总

2019/7/23 21:17:21 人评论 次浏览 分类:学习教程

线性表

  1. 初始化:给线性表中的相关参数赋值
  2. 求长度:求线性表中的元素的个数
  3. 取元素:取给定位置的元素值
  4. 查元素:查找给定元素值的位置
  5. 插入元素:在指定的位置插入给定的值
  6. 删除:删除指定位置的值或者是删除给定的值。
  7. 遍历元素:从头到尾扫描线性表。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;//假定线性表的元素类型为整型
#define LIST_SIZE 1024 //假定我们的线性表长度是1024
#define TRUE 1
#define FALSE 0
typedef struct {
	ElemType data[LIST_SIZE];
	int last;//指向最后一个节点的位置
}SequenList;



//last的存在的目的:为了在函数调用的时候传递数据方便,因为我们与分配
//的空间中,并不是立即存满的

///数组顺序表的实现初始化
///获得一个长度为0的数组
SequenList* InitSeq();


///求长度:求线性表中的元素的个数
///获得当前数组顺序表的元素个数,pList:顺序表的起始地址
int GetSizeSeq(SequenList* pList);

///取元素:取给定位置的元素值
///返回值是元素值
///pList:目标的顺序表, pos:获取元素的下标 ,e:将元素值放入
int GetElemSqList(SequenList* pList, int pos, ElemType *e);

///	查元素:查找给定元素值的位置
///相同值只去第一个
///返回值:-1表示没有找到,否则返回带查找元素的角标
///pList:传入的数组顺序表,Key比对的值
int LocateElemSqList(SequenList* pList, ElemType key);

///	插入元素:在指定的位置插入给定的值
/// 插入的位置为k:k: 0 -- n-1
//pList:目标顺序表,x待插入的元素,k插入的位置
int InsertElemSqList(SequenList* pList, ElemType x, int k);

///删除:删除指定位置的值或者是删除给定的值。
//pList:目标顺序数组,k表示需要删除的位置
int DelElemSqList(SequenList *pList, int k);

///遍历元素:从头到尾扫描线性表。
///pList:目标顺序数组
void showSeqList(SequenList* pList);

数组形式顺序表


#include "SeqList.h"

*/
SequenList* lPtr;
//实现初始化
SequenList* InitSeq() {
	SequenList *pList=NULL;
	pList = (SequenList *)malloc(sizeof(SequenList));
	if (pList != NULL)
		pList->last = 0;//初始化成功,且长度为0

	return pList;
}
//SequenList seqenList;
//SequenList *seqenList;
//前者分配空间了,而后者没有空间


//求长度:求线性表中的元素的个数
int GetSizeSeq(SequenList* pList) {
	return pList->last;
}

//取元素:取给定位置的元素值
/// pList:目标的顺序表, pos:获取元素的下标 ,e:将元素值放入
int GetElemSqList(SequenList* pList, int pos, ElemType *e) {
	if (pos<0 || pos>pList->last) {
		return FALSE;
	}
	if (pList->last <= 0)
		return FALSE;
	//说明此时pos在0 -- n之间
	*e = pList->data[pos];
	return TRUE;
}

//	查元素:查找给定元素值的位置
//相同值只去第一个
//返回值:-1表示没有找到,否则返回带查找元素的角标
//pList:传入的数组顺序表,Key比对的值
int LocateElemSqList(SequenList* pList, ElemType key) {
	int i;
	for (i = 0;i < pList->last;i++) {
		if (pList->data[i] == key)
			return i;
	}
	return -1;
}

//	插入元素:在指定的位置插入给定的值
// 插入的位置为k:k: 0 -- n-1
// 顺序表:不满
//pList:目标顺序表,x待插入的元素,k插入的位置
int InsertElemSqList(SequenList* pList, ElemType x, int k) {
	int j;
	//顺序表尚未填满
	if (pList->last >= LIST_SIZE - 1)
		return FALSE;
	//表明K是有效位置
	if (k<0 || k>(pList->last + 1))
		return FALSE;
	for (j = pList->last;j >= k;j--) {
		pList->data[j + 1] = pList->data[j];
	}
	pList->data[k] = x;
	pList->last = pList->last + 1;
	return TRUE;
}

//删除:删除指定位置的值或者是删除给定的值。
//pList:目标顺序数组,k表示需要删除的位置
int DelElemSqList(SequenList *pList, int k) {
	if ((k >= 0 && k <= pList->last) && (pList->last != 0)) {
		for (int j = k;j <= pList->last;j++) {
			pList->data[j] = pList->data[j + 1];
		}
		pList->last--;
		return TRUE;
	}
	return FALSE;
}

//遍历元素:从头到尾扫描线性表。
void showSeqList(SequenList* pList) {
	for (int i = 0;i < pList->last;i++) {
		printf(" %d", pList->data[i]);
	}
}


int main1(void) {
	lPtr = InitSeq();//这样是否可以=>可以的,且使用NULL来判断是否初始化完毕
	if (lPtr) {
		//todo:继续使用这个顺序表
		for (int i = 0;i < 10;i++) {
			InsertElemSqList(lPtr, i, i);
		}
		printf("初始化后顺序表的元素个数:%d", GetSizeSeq(lPtr));
		printf("************\n");
		showSeqList(lPtr);
		InsertElemSqList(lPtr, 2000, 0);
		printf("初始化后顺序表的元素个数:%d", GetSizeSeq(lPtr));
		printf("************\n");
		showSeqList(lPtr);
		DelElemSqList(lPtr, 1);
		printf("初始化后顺序表的元素个数:%d", GetSizeSeq(lPtr));
		printf("************\n");
		showSeqList(lPtr);
		int pos = LocateElemSqList(lPtr, 16);
		if (pos >= 0) {
			printf("当前元素位于%d", pos);
		}
		else {
			printf("没有找到这个元素");
		}
		printf("************\n");
		showSeqList(lPtr);
		
	}
	else {
		//todo:提示没有可以使用的空间
	}
	getchar();
	getchar();
	return 0;
}

单链表


#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef int ElemType;//假定线性表的元素类型为整型

//定义节点
typedef struct node {
	int data;
	struct node *pNext;
}LinkListNode;

///创建带有头节点的链表Init
///函数的返回值是头节点,没有参数
LinkListNode* InitLinkList(void);
///求长度:求顺序表中的元素的个数
///函数的返回值是顺序表的长度,参数pHead:是单链表的头节点
int GetSizeLinkList(LinkListNode* pHead);
///取元素:取给定位置的元素值
///返回值:第i个元素的地址,pHead:头指针,i 待查节点的序号
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos);

///查元素:查找给定元素值的位置
///返回值:节点的地址,找不到就返回NULL
///pHead:单链表的头指针,objData:是需要匹配的元素值
LinkListNode* LocateLinkList(LinkListNode* pHead, int objData);

///插入元素:在指定的位置插入给定的值
///尾插法建立单链表(将逻辑上的顺序表放入单链表的物理结构当中)
///返回值:链表的头指针,arr:传入的顺序表,length:顺序表的长度
LinkListNode* Create_Rear_LkList(ElemType arr[], int length);

///头插法建立单链表
///返回值:链表的头指针,arr:传入的顺序表,length:顺序表的长度
LinkListNode* Create_Front1_LkList(ElemType arr[], int length);
///头插法2
///返回值:链表的头指针,arr:传入的顺序表,length:顺序表的长度
LinkListNode* Create_Front2_LkList(ElemType arr[], int length);

///头插法建立
///返回值:链表的头指针,arr:传入的顺序表,length:顺序表的长度
LinkListNode* Create_Front3_LkList(ElemType arr[], int length);


///插入元素:在指定的位置插入给定的值
//ptr:带插入的元素位置,将在ptr的后继结点中插入,x:插入的值
void Insert_After_LkList(LinkListNode* ptr, ElemType x);

///指定位置之前插入
///pHead:链表的头指针,ptr:带插入的元素位置,x:插入的值
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x);


///删除节点:Ptr是需要删除的节点,将删除ptr的后续节点
///返回值是带删除的节点位置
LinkListNode* Delete_After_LkList(LinkListNode* ptr);

///删除第i个节点
///返回值是带删除的节点位置,pHead:头节点,i是第i个元素
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i);

///遍历
void ShowLkList(LinkListNode* pHead);
#include "LinkList.h"

///创建带有头节点的链表Init
LinkListNode* InitLinkList(void) {
	LinkListNode* pHead = NULL;
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	if (pHead) {
		pHead->pNext = NULL;
	}
	return pHead;
}
//求长度:求线性表中的元素的个数
int GetSizeLinkList(LinkListNode* pHead) {
	int n = 0;
	while (pHead->pNext) {
		n++;
		pHead = pHead->pNext;
	}
	return n;
}

//取元素:取给定位置的元素值
//输入链表的头指针,要查找的编号,输出第i个元素的地址
///pHead:头指针,i 待查节点的序号
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos) {
	int j;
	LinkListNode* p;
	p = pHead;
	j = 0;
	if(pos == 0)
		return NULL;
	while (j < pos && p->pNext != NULL) {
		p = p->pNext;
		j++;
	}
	if (pos == j)
		return p;
	else
		return NULL;
}

//查元素:查找给定元素值的位置
///找到就返回节点的地址,找不到就返回NULL
LinkListNode* LocateLinkList(LinkListNode* pHead, int objData) {
	LinkListNode* p;
	p = pHead->pNext;//跳过头节点
	while (p != NULL && p->data != objData) {
		p = p->pNext;
	}
	return p;

}

//插入元素:在指定的位置插入给定的值
//因为链表这种结构的内存是由程序员管理的,因此它的建立有一定的运算
//方法
///尾插法建立单链表(将逻辑上的顺序表放入单链表的物理结构当中)
//arr:传入的顺序表,length:顺序表的长度
LinkListNode* Create_Rear_LkList(ElemType arr[], int length) {
	LinkListNode* pHead, *p, *q;
	int i;//循环变量,用来遍历全部的顺序表

	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));

	q = pHead; //q是获得了当前链表的头节点
	//q保存了pHead,同时通过q不断前移使得链表串联起来
	for (i = 0;i < length;i++) {
		//获得一个单链表的节点,将这个节点加入到有
		//pHead指向的这个链表当中
		p = (LinkListNode*)malloc(sizeof(LinkListNode));
		//p获得一个可以加入链表的节点单元
		p->data = arr[i];//将顺序表的内容存入单链表的节点

		q->pNext = p;//
		q = p;
	}
	p->pNext = NULL;
	return pHead;

}

///头插法建立单链表
LinkListNode* Create_Front1_LkList(ElemType arr[], int length) {
	LinkListNode* pHead, *p, *q;
	int i;
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = NULL;
	q = pHead->pNext;
	//头插的时候,必须逆序遍历顺序表
	for (i = length - 1;i >= 0;i--) {
		p = (LinkListNode*)malloc(sizeof(LinkListNode));
		p->data = arr[i];
		p->pNext = q;//是的新加入的节点传入了上一个节点
		pHead->pNext = p;//头节点指向了当前的新加入节点
		q = pHead->pNext;//让q指向当前的节点
	}
	return pHead;
}
///头插法2
LinkListNode* Create_Front2_LkList(ElemType arr[], int length) {
	LinkListNode* pHead, *p, *q;
	//p是新加入节点,q是当前节点
	int i;
	q = NULL;
	for (i = length - 1;i >= 0;i--) {
		p = (LinkListNode*)malloc(sizeof(LinkListNode));
		p->data = arr[i];
		p->pNext = q;
		q = p;
	}
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = q;
	return pHead;
}

///头插法建立
LinkListNode* Create_Front3_LkList(ElemType arr[], int length) {
	LinkListNode* pHead, *p;
	int i;
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = NULL;
	for (i = length - 1;i >= 0;i--) {
		p = (LinkListNode*)malloc(sizeof(LinkListNode));
		p->data = arr[i];
		p->pNext = pHead->pNext;
		pHead->pNext = p;
	}
	//之所以我们的方法三可以节省方法一中的一个变量q
	//原因是:pHead不发生变化,而pHead中的pNext始终作为当前节点的指针
	return pHead;
}

/*
顺序表:12,33,44,76,89,90(逻辑上的顺序表)=>单链表
本例中,我们用数组表示这种顺序表
*/


//插入元素:在指定的位置插入给定的值
//在指定位置之后插入
void Insert_After_LkList(LinkListNode* ptr, ElemType x) {
	LinkListNode* s;
	s = (LinkListNode*)malloc(sizeof(LinkListNode));
	s->data = x;
	s->pNext = ptr->pNext;
	ptr->pNext = s;
}

//指定位置之前插入
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x) {
	LinkListNode* s, *qPtr;
	s = (LinkListNode*)malloc(sizeof(LinkListNode));
	s->data = x;
	qPtr = pHead;//qPtr是用来代替pHead的移动的,ptr是目标节点
	while (qPtr->pNext != ptr)
		qPtr = qPtr->pNext;
	s->pNext = ptr;
	qPtr->pNext = s;
	//因为链表是单向的,虽然我知道当前节点是ptr
	//但是在语法层面上,我如果想知道ptr的前继节点只能从head遍历而来
	//查到了当前节点的前继,才能使用后插的方法完成节点的加入
}


//删除:删除指定位置的值或者是删除给定的值。
//情形一:删除指定节点的后继结点
//情形二:删除第i个节点,假定头节点i=0
//删除返回目标节点的地址,并不涉及到动态空间的回收
//在动态回收空间的要求中,应该遵循的原理是谁污染谁治理
//在顺序表中的删除就是逻辑上的删除,就是说我们的这个节点不再
//存在于当前的顺序表中了
///删除节点:Ptr是需要删除的节点,将删除ptr的后续节点
LinkListNode* Delete_After_LkList(LinkListNode* ptr) {
	LinkListNode* fptr;
	//假定我们的顺序表A-》B-》C,我们要删除的是A的后续节点B,A-》C
	fptr = ptr->pNext;// ptr是A,所以ptr的next是B,所以fptr是B
	ptr->pNext = fptr->pNext;//ptr是A,fptr是B,所以fptr的next是C,所以ptr-next就变成C
	return fptr;
}

///删除第i个节点
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i) {
	LinkListNode*ptr, *qPtr = NULL;
	ptr = GetLinkListNode(pHead, i - 1);//找到i的前继节点
	if (ptr != NULL && ptr->pNext != NULL)
		qPtr = Delete_After_LkList(ptr);
	return qPtr;
}
//遍历
void ShowLkList(LinkListNode* pHead) {
	LinkListNode* p = pHead->pNext;
	while (p != NULL) {
		printf(" %d", p->data);
		p = p->pNext;
	}
}

int main3(void) {
	ElemType MySeq[] = { 1,2,3,4,5 };
	LinkListNode* pHead = Create_Rear_LkList(MySeq, 5);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	LinkListNode* pPos = GetLinkListNode(pHead, 2);
	Insert_After_LkList(pPos, 999);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	Insert_Before_LkList(pHead, pPos, 666);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	//Delete_After_LkList(pPos);
	Delete_i_LkList(pHead, 2);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	printf("\nList Size:%d", GetSizeLinkList(pHead));
	getchar();
	return 0;
}

顺序表转置

////设有一个顺序表,其数据为a,b,c,d,e,f,g,要求将其就地转置成g,f,e,d,c,b,a
////要求逆转表仍然占据原空间
//#include "SeqList.h"
//SequenList* pGlobalSeq;
//
//void RevseSeqList(SequenList* pList) {
//	int temp;
//	int count, i;
//	if (pList->last == 0 || pList->last == 1)
//		return;
//	count = pList->last / 2;
//	for (i = 0;i < count;i++) {
//		temp = pList->data[i];
//		pList->data[i] = pList->data[pList->last - 1 - i];
//		pList->data[pList->last - 1 - i] = temp;
//	}
//}
//int main(void) {
//	pGlobalSeq=InitSeq();
//	for (int i = 0;i < 10;i++) {
//		InsertElemSqList(pGlobalSeq, i * 2, i);
//	}
//	printf("\n**********当前的顺序表元素********\n");
//	showSeqList(pGlobalSeq);
//	RevseSeqList(pGlobalSeq);
//	printf("\n**********当前的顺序表元素********\n");
//	showSeqList(pGlobalSeq);
//	free(pGlobalSeq);
//	getchar();
//	return 0;
//}
//Ctrl+a Ctrl+k Ctrl+C

#include "LinkList.h"

LinkListNode* ReverseLkList(LinkListNode* pHead) {
	LinkListNode* Pointer, *Next;//Pointer是将来依次获得的当前节点
	//Next:将来获得的当前节点的原先的下一个节点
	LinkListNode* Back; //原先节点的上一个节点
	//step 1: 将原先的next节点的next域变为pointer
	//step 2:将原先的pointer的next域变成back

	Back = pHead; //原先就是从头节点开始,因此,我们首先将back作为头节点
	Pointer = Back->pNext;//通过头节点获得了第一个元素=>pointer指向第一个元素

	Next = Pointer->pNext;//此时pointer是第一个元素,因此它的pNext是第二个元素
	Pointer->pNext = Back;//pointer->pNext域变成了Back,又因为Back是头节点,所以
	//此时原先的第一个元素的后继已经变成了原先的头节点
	Back = Pointer;//pointer是第一个元素,因此,此时Back变成了第一个元素
	Pointer = Next;//因为在46行,Next已经是第二个元素了,
	//因此,此时pointer指向了第二个元素

	//在46行,Next变成了原先的第二个元素,有因为在46行-51行,没有在对Next的pNext域
	//进行操作,因此,原先链表中的后继信息没有破坏
	//47行,pointer作为当前元素指向了原先的前继节点的时候,此时,当前元素把原先的前继元素
	//变成了后续节点
	//48行,再将Back设为当前元素,49行将Pointer设为下一个元素

	while (Pointer->pNext != NULL) {
		Next = Pointer->pNext;
		Pointer->pNext = Back;
		Back = Pointer;
		Pointer = Next;
	}

	Pointer->pNext = Back;
	//此时Pointer已经是原先链表中的最后一个元素了,
	//因此,必须要把Pointer和原先的前继节点联系起来,而原先的前继节点一定在Back

	//此时反转完毕,我们需要重新设置头节点
	//原先的pHead没有变,因此原先的pHead->pNext指向的原先的第一个元素
	//但是现在我们要让这个元素的pNext域置为空
	pHead->pNext->pNext = NULL;
	//由于pHead没有变,所以我们依然让它作为反转后链表的头节点
	//所以将当前的首元素放置它的pnext域中
	pHead->pNext = Pointer;

	return pHead;



}
int mainAAA(void) {
	LinkListNode* pHead = NULL;
	int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
	pHead = Create_Rear_LkList(arr, 10);
	printf("\n************当前的元素有\n");
	ShowLkList(pHead);
	
	pHead = ReverseLkList(pHead);
	printf("\n************当前的元素有\n");
	ShowLkList(pHead);
	getchar();
	return 0;
}

 

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->