博客

数据结构 – 线性表（C语言版）

  • Post author:
  • Post category:其他


线性表分为

顺序表

和

单链表

线性表的操作主要是

查询、插入、删除



1、顺序表

  • 首先，定义一个顺序表的结构体 
#define MAX_SIZE 10
typedef struct {
	int data[MAX_SIZE];
	int length;
}SqList, * PsqList;
  • 创建一个顺序表

在这里插入图片描述 

//创建顺序表
void createSqList(PsqList pSqList) {
	pSqList->length = 0;
	for (int i = 0; i < MAX_SIZE - 5; i++) {
		pSqList->data[i] = (i + 1) * 3;
		pSqList->length++;
	}
}
  • 遍历顺序表 
//遍历顺序表
void displaySqList(PsqList pSqList) {
	printf("\tSqList Length: %d\n", pSqList->length);
	for (int i = 0; i < pSqList->length; i++) {
		printf("\t%d", pSqList->data[i]);
	}
	printf("\n");
}



1.1、查询

  • 顺序查询 
#include <string.h>
//根据数值查询位置
const char* queryPositionByValue(PsqList pSqList, int value) {
	char bf[100];
	sprintf_s(bf, "表中没有数据 %d\n", value);
	const char* result = _strdup(bf);
	for (int i = 0; i < pSqList->length; i++) {
		if (pSqList->data[i] == value) {
			char buffer[100];
			sprintf_s(buffer, "数据 %d 在表中的位置 %d\n", value, i+1);
			result = _strdup(buffer);
			return result;
		}
	}
	return result;
}
  • 输出结果 
int main() {
	PsqList pL = (PsqList)malloc(sizeof(SqList));
	createSqList(pL);
	displaySqList(pL);

	const char* res1 = queryPositionByValue(pL, 3);
	printf("\n\t%s\n", res1);

	const char* res2 = queryPositionByValue(pL, 9);
	printf("\t%s\n", res2);

	const char* res3 = queryPositionByValue(pL, 15);
	printf("\t%s\n", res3);

	const char* res4 = queryPositionByValue(pL, 20);
	printf("\t%s\n", res4);

	return 0;
}

在这里插入图片描述



1.2、插入

在这里插入图片描述

  • 在position处插入元素
  • 位置position在表中对应的序号 i = position-1
  • 思路：将v(length-1)至vi依次后移一位，然后将新数据插入vi 
//在指定位置插入元素
void insertElementByPosition(PsqList pSqList, int position, int element) {
	if (position > MAX_SIZE || position < 1) {
		return;
	}

	if (pSqList->length >= MAX_SIZE) {
		return;
	}

	if (position == pSqList->length + 1) {
		pSqList->data[pSqList->length] = element;
		pSqList->length++;
		return;
	}

	int i = position - 1;
	for (int j = pSqList->length - 1; j >= i; j--) {
		pSqList->data[j + 1] = pSqList->data[j];
	}
	pSqList->data[i] = element;
	pSqList->length++;
}
  • 输出结果 
int main() {
	PsqList pL = (PsqList)malloc(sizeof(SqList));
	createSqList(pL);
	printf("\n");
	displaySqList(pL);

	int position1 = 1;
	int v1 = 111;
	insertElementByPosition(pL, position1, v1);
	printf("\n\t在第 %d 个位置插入 %d\n", position1, v1);
	displaySqList(pL);

	int position2 = 3;
	int v2 = 333;
	insertElementByPosition(pL, position2, v2);
	printf("\n\t在第 %d 个位置插入 %d\n", position2, v2);
	displaySqList(pL);


	int position3 = 7;
	int v3 = 777;
	insertElementByPosition(pL, position3, v3);
	printf("\n\t在第 %d 个位置插入 %d\n", position3, v3);
	displaySqList(pL);


	int position4 = 9;
	int v4 = 999;
	insertElementByPosition(pL, position4, v4);
	printf("\n\t在第 %d 个位置插入 %d\n", position4, v4);
	displaySqList(pL);
	
	return 0;
}

在这里插入图片描述



1.3、删除

在这里插入图片描述

  • 删除position处的元素
  • 位置position在表中对应的序号 i = position-1
  • 思路：将v(i+1)至v(length-1)依次向前移动一位 
//删除指定位置的元素
void deleteElementByPosition(PsqList pSqList, int position) {
	if (position < 1 || position > MAX_SIZE) {
		return;
	}

	if (position > pSqList->length) {
		return;
	}

	int i = position - 1;

	for (int j = i; j < pSqList->length - 1; j++) {
		pSqList->data[j] = pSqList->data[j + 1];
	}
	pSqList->length--;
}
  • 运行结果 
int main() {
	PsqList pL = (PsqList)malloc(sizeof(SqList));
	createSqList(pL);
	printf("\n");
	displaySqList(pL);

	int position1 = 1;
	deleteElementByPosition(pL,position1);
	printf("\n\t删除第 %d 个位置元素\n", position1);
	displaySqList(pL);

	int position2 = 2;
	deleteElementByPosition(pL, position2);
	printf("\n\t删除第 %d 个位置元素\n", position2);
	displaySqList(pL);

	int position3 = 3;
	deleteElementByPosition(pL, position3);
	printf("\n\t删除第 %d 个位置元素\n", position3);
	displaySqList(pL);

	return 0;
}

在这里插入图片描述



1.4、合并两个顺序表

//合并两个顺序表
PsqList megerSqList(PsqList pLA, PsqList pLB) {

	PsqList pLC = (PsqList)malloc(sizeof(SqList));
	pLC->length = pLA->length + pLB->length;

	int* pa = pLA->data;
	int* pb = pLB->data;
	int* pc = pLC->data;


	int* paEnd = pa + pLA->length - 1;
	int* pbEnd = pb + pLB->length - 1;


	while (pa <=paEnd && pb <= pbEnd)
	{
		if (*pa <= *pb) {
			*pc++ = *pa++;
		}
		else {
			*pc++ = *pb++;
		}
	}

	while (pa <= paEnd) *pc++ = *pa++;
	while (pb <= pbEnd) *pc++ = *pb++;

	return pLC;
}

int main() {
	PsqList pLA = (PsqList)malloc(sizeof(SqList));
	createSqList(pLA);
	printf("\n");
	displaySqList(pLA);


	PsqList pLB = (PsqList)malloc(sizeof(SqList));
	createSqListB(pLB);
	printf("\n");
	displaySqList(pLB);



	PsqList pLC = megerSqList(pLA, pLB);
	printf("\t合并后\n");
	displaySqList(pLC);

	return 0;
}
  • 输出结果

    在这里插入图片描述



2、单链表

  • 首先创建一个链表结构体 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
  • 遍历链表 
//遍历链表
void displayLinkList(LinkList p) {
	printf("\n");
	while (p != NULL) {
		printf("\t%d", p->data);
		p = p->next;
	}
	printf("\n");
}



2.1、创建单链表



（1）头插法

  • 创建链表 
//头插法
void createLinkByHead(LinkList& linkList) {

	linkList = (LinkList)malloc(sizeof(LNode));
	linkList->data = 100;
	linkList->next = NULL;

	for (int i = 0; i < 5; i++) {
		LinkList p = (LinkList)malloc(sizeof(LNode));
		p->data = (i + 2) * 100;
		p->next = linkList->next;
		linkList->next = p;
	}
}

在这里插入图片描述

  • 输出结果 
int main() {
	LinkList L1;
	createLinkByHead(L1);
	displayLinkList(L1);
	displayLinkList(L1);
	return 0;
}

在这里插入图片描述



（2）尾插法

  • 创建链表 
//尾插法
void createLinkByTail(LinkList& linkList) {

	linkList = (LinkList)malloc(sizeof(LNode));
	linkList->data = 100;
	linkList->next = NULL;
	LinkList pre = linkList;
	for (int i = 0; i < 5; i++) {
		LinkList p = (LinkList)malloc(sizeof(LNode));
		p->data = (i + 2) * 100;
		pre->next = p;
		p->next = NULL;
		pre = p;
	}
}

在这里插入图片描述

  • 输出结果 
int main() {
	LinkList L2;
	createLinkByTail(L2);
	displayLinkList(L2);
	displayLinkList(L2);
	return 0;
}

在这里插入图片描述



2.2、通过序号查找

//通过序号查找
LinkList queryByIndex(LinkList linkList, int index) {
	LinkList p = linkList;
	int i = 0;
	while (i < index) {
		p = p->next;
		i++;
	}
	return p;
}
  • 输出结果 
int main() {
	LinkList L;
	createLinkByTail(L);
	displayLinkList(L);

	int position = 3;
	LinkList p= queryByIndex(L, position-1);
	printf("\n\t第 %d 个元素的值是 %d\n", position, p->data);
	return 0;
}

在这里插入图片描述



2.3、通过序号插入

//通过序号插入
LinkList insertByIndex(LinkList linkList, int index, int data) {

	LinkList pEle = (LinkList)malloc(sizeof(LNode));
	pEle->data = data;
	pEle->next = NULL;

	LinkList pre = linkList;
	LinkList p = pre;
	if (index == 0){
		pEle->next = pre;
		linkList = pEle;
	}
	else {
		for (int i = 0; i < index; i++) {
			pre = p;
			p = p->next;
		}
		pre->next = pEle;
		pEle->next = p;
	}
	return linkList;
}
  • 输出结果 
int main() {
	LinkList L;
	createLinkByTail(L);
	displayLinkList(L);


	int positionInsert1 = 3;
	printf("\n\t在第 %d 个位置插入\n", positionInsert1);
	LinkList LInsert1 = insertByIndex(L, positionInsert1 - 1, 333);
	displayLinkList(LInsert1);

	int positionInsert2 = 1;
	printf("\n\t在第 %d 个位置插入\n", positionInsert2);
	LinkList LInsert2 = insertByIndex(LInsert1, positionInsert2 - 1, 111);
	displayLinkList(LInsert2);


	int positionInsert3 = 8;
	printf("\n\t在第 %d 个位置插入\n", positionInsert3);
	LinkList LInsert3 = insertByIndex(LInsert2, positionInsert3 - 1, 888);
	displayLinkList(LInsert3);


	int positionInsert4 = 10;
	printf("\n\t在第 %d 个位置插入\n", positionInsert4);
	LinkList LInsert4 = insertByIndex(LInsert3, positionInsert4 - 1, 101010);
	displayLinkList(LInsert4);

	return 0;
}

在这里插入图片描述



2.4、通过序号删除

//通过序号删除
LinkList deleteByIndex(LinkList linkList, int index) {

	LinkList pre = linkList;

	if (index == 0) {
		linkList = linkList->next;
		pre->next = NULL;
		free(pre);
	}
	else {
		LinkList p = pre;
		for (int i = 0; i < index; i++) {
			pre = p;
			p = p->next;
		}
		pre->next = p->next;
		p->next = NULL;
		free(p);

	}
	return linkList;
}
  • 输出结果 
int main() {
	LinkList L;
	createLinkByTail(L);
	displayLinkList(L);


	int positionDel1 = 3;
	printf("\n\t删除第 %d 个元素的值\n", positionDel1);
	LinkList LDel1= deleteByIndex(L, positionDel1 - 1);
	displayLinkList(LDel1);

	int positionDel2 = 1;
	printf("\n\t删除第 %d 个元素的值\n", positionDel2);
	LinkList LDel2 = deleteByIndex(LDel1, positionDel2 - 1);
	displayLinkList(LDel2);

	int positionDel3 = 4;
	printf("\n\t删除第 %d 个元素的值\n", positionDel3);
	LinkList LDel3 = deleteByIndex(LDel2, positionDel3 - 1);
	displayLinkList(LDel3);


	return 0;
}

在这里插入图片描述



2.5、合并两个单链表

//合并两个单链表
LinkList megerLinkList(LinkList LA, LinkList LB) {

	LinkList LC = (LinkList)malloc(sizeof(LNode));
	LinkList pc = LC;

	while (LA && LB)
	{
		if (LA->data <= LB->data)
		{
			pc->next = LA;
			pc = LA;
			LA = LA->next;
		}
		else {
			pc->next = LB;
			pc = LB;
			LB = LB->next;
		}
	}


	if (LA) pc->next = LA;
	if (LB) pc->next = LB;


	pc = LC;
	LC = LC->next;
	pc->next = NULL;
	free(pc);
	return LC;
}

int main() {
	LinkList L1;
	createLinkByTail(L1);
	displayLinkList(L1);

	LinkList L2;
	createLinkByTailB(L2);
	displayLinkList(L2);

	LinkList L3 = megerLinkList(L1, L2);
	displayLinkList(L3);

	return 0;
}
  • 输出结果

在这里插入图片描述


版权声明：本文为weixin_41733225原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。