线性结构：顺序表和链表

一、顺序表

#include <stdio.h>
#include <stdlib.h>

typedef struct TABLE
{
	int* pHead;
	int length;
	int size;
}Table;

#define LENGTH 5

Table InitTable()
{
	Table t;
	t.pHead = (int*)malloc(sizeof(int) * LENGTH);
	if (!t.pHead)
	{
		printf("初始化失败\n");
		exit(0);
	}
	t.length = LENGTH;
	t.size = 0;

	return t;
}

//遍历
void DisplayTable(Table t)
{
	if (t.pHead == NULL || t.length == 0)
	{
		return 0;
	}
	for (int i = 0; i < t.size; i++)
	{
		printf("%d   ", t.pHead[i]);
	}
	printf("\n");
}


//插入
void InsertTable(Table* pT, int value, int n)
{
	//判断插入位置
	if (!pT || !pT->pHead)
	{
		return;
	}
	if (n-1 > pT->size || n < 1)
	{
		return;
	}
	//判断空间是否够用
	if (pT->size == pT->length)
	{
		//不够
		pT->pHead = (int*)realloc(pT->pHead, sizeof(int) * (pT->length + 1));
		pT->length++;
		if (pT->pHead == NULL)
		{
			printf("扩容失败\n");
			exit(0);
		}
	}
		//插入
		for (int i = pT->size; i >= n; i--)
		{
			pT->pHead[i] = pT->pHead[i - 1];
		}
		pT->pHead[n - 1] = value;
		pT->size++;
}


//删除
void DeleteTable(Table* pT, int n)
{
	if (n > pT->size || n < 1)
	{
		printf("删除位置有误\n");
		return;
	}
	for (int i = n - 1; i < pT->size - 1; i++)
	{
		pT->pHead[i] = pT->pHead[i + 1];
	}
	pT->size--;
}
int main()
{
	Table t = InitTable();

	for (int i = 0; i < 5; i++)
	{
		InsertTable(&t, i + 10, i + 1);
	}
	DisplayTable(t);
	InsertTable(&t, 15, 6);
	DisplayTable(t);
	InsertTable(&t, 5, 3);
	DisplayTable(t);

	DeleteTable(&t, 5);
	DisplayTable(t);
	return 0;
}

输出：

10   11   12   13   14
10   11   12   13   14   15
10   11   5   12   13   14   15
10   11   5   12   14   15

D:\数据结构\线性表\顺序表和链表\x64\Debug\顺序表和链表.exe (进程 20564)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

二、链表

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE
{
	int value;
	struct NODE* pNext;
}Node;

typedef struct LIST
{
	Node* pHead;
	Node* pEnd;
	int size;
}List;

List InitList()
{
	List lst;
	lst.pHead = NULL;
	lst.pEnd = NULL;
	lst.size = 0;
	return lst;
}
void AddNode(List* plst,int value)
{
	if (plst == NULL)
	{
		printf("链表不存在\n");
		return;
	}
	Node* pTemp = (Node*)malloc(sizeof(Node));
	pTemp->value = value;
	pTemp->pNext = NULL;
	if (plst->pHead == NULL)
	{
		plst->pHead = pTemp;
	}
	else
	{
		(plst->pEnd)->pNext = pTemp;
	}
	plst->pEnd = pTemp;
  plst->size++;
}
void ShowList(List lst)
{
	while (lst.pHead)
	{
		printf("%d   ", lst.pHead->value);
		lst.pHead = lst.pHead->pNext;
	}
	printf("\n");
}

void ReversalShowList(Node* pHead)
{
	if (!pHead)
	{
		return;
	}
	ReversalShowList(pHead->pNext);
	printf("%d   ", pHead->value);
	
}
 
 
 
void Reverse(List* plst)
{
	if (plst->pHead == NULL || plst->pHead->pNext == NULL)
	{
		return;
	}
	Node* pBegin = NULL;
	Node* pMid = plst->pHead;
	Node* pEnd = plst->pHead->pNext;

	plst->pHead = plst->pEnd;
	plst->pEnd = pMid;
	while (pEnd != NULL)
	{
		pMid->pNext = pBegin;
		pBegin = pMid;
		pMid = pEnd;
		pEnd = pEnd->pNext;
	}
	pMid->pNext = pBegin;
}
 
 
 
 
void Reverse1(List* plst)
{
	if (plst == NULL || plst->pHead == NULL || plst->pHead->pNext == NULL)
	{
		return;
	}
	Node* pNewHead = NULL;
	plst->pEnd = plst->pHead;
	while (plst->pHead != NULL)
	{
		Node* pTemp = plst->pHead;
		plst->pHead = plst->pHead->pNext;
		pTemp->pNext = pNewHead;
		pNewHead = pTemp;
	}
	plst->pHead = pNewHead;
}



int main()
{

	List lst = InitList();

	AddNode(&lst, 1);
	AddNode(&lst, 2);
	AddNode(&lst, 3);
	AddNode(&lst, 4);

	ShowList(lst);
	//ReversalShowList(lst.pHead);
	Reverse(&lst);
	ShowList(lst);

	Reverse1(&lst);
	ShowList(lst);
	return 0;
}

输出：

1   2   3   4
4   3   2   1
1   2   3   4

D:\数据结构\线性表\顺序表和链表\x64\Debug\顺序表和链表.exe (进程 18412)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .