线性表分为顺序表和单链表
线性表的操作主要是查询、插入、删除
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;
}
文章来源:https://www.toymoban.com/news/detail-550121.html
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;
}
- 输出结果
文章来源地址https://www.toymoban.com/news/detail-550121.html
到了这里,关于数据结构 - 线性表(C语言版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!