線性表分為順序表和單鏈表
線性表的操作主要是查詢、插入、刪除
1、順序表
- 首先，定義一個(gè)順序表的結(jié)構(gòu)體
#define MAX_SIZE 10
typedef struct {
int data[MAX_SIZE];
int length;
}SqList, * PsqList;
- 創(chuàng)建一個(gè)順序表
//創(chuàng)建順序表
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>
//根據(jù)數(shù)值查詢位置
const char* queryPositionByValue(PsqList pSqList, int value) {
char bf[100];
sprintf_s(bf, "表中沒有數(shù)據(jù) %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, "數(shù)據(jù) %d 在表中的位置 %d\n", value, i+1);
result = _strdup(buffer);
return result;
}
}
return result;
}
- 輸出結(jié)果
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在表中對應(yīng)的序號 i = position-1
- 思路：將v(length-1)至vi依次后移一位，然后將新數(shù)據(jù)插入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++;
}
- 輸出結(jié)果
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 個(gè)位置插入 %d\n", position1, v1);
displaySqList(pL);
int position2 = 3;
int v2 = 333;
insertElementByPosition(pL, position2, v2);
printf("\n\t在第 %d 個(gè)位置插入 %d\n", position2, v2);
displaySqList(pL);
int position3 = 7;
int v3 = 777;
insertElementByPosition(pL, position3, v3);
printf("\n\t在第 %d 個(gè)位置插入 %d\n", position3, v3);
displaySqList(pL);
int position4 = 9;
int v4 = 999;
insertElementByPosition(pL, position4, v4);
printf("\n\t在第 %d 個(gè)位置插入 %d\n", position4, v4);
displaySqList(pL);
return 0;
}
1.3、刪除
- 刪除position處的元素
- 位置position在表中對應(yīng)的序號 i = position-1
- 思路：將v(i+1)至v(length-1)依次向前移動(dòng)一位
//刪除指定位置的元素
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--;
}
- 運(yùn)行結(jié)果
int main() {
PsqList pL = (PsqList)malloc(sizeof(SqList));
createSqList(pL);
printf("\n");
displaySqList(pL);
int position1 = 1;
deleteElementByPosition(pL,position1);
printf("\n\t刪除第 %d 個(gè)位置元素\n", position1);
displaySqList(pL);
int position2 = 2;
deleteElementByPosition(pL, position2);
printf("\n\t刪除第 %d 個(gè)位置元素\n", position2);
displaySqList(pL);
int position3 = 3;
deleteElementByPosition(pL, position3);
printf("\n\t刪除第 %d 個(gè)位置元素\n", position3);
displaySqList(pL);
return 0;
}
1.4、合并兩個(gè)順序表
//合并兩個(gè)順序表
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;
}
- 輸出結(jié)果
2、單鏈表
- 首先創(chuàng)建一個(gè)鏈表結(jié)構(gòu)體
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、創(chuàng)建單鏈表
（1）頭插法
- 創(chuàng)建鏈表
//頭插法
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;
}
}
- 輸出結(jié)果
int main() {
LinkList L1;
createLinkByHead(L1);
displayLinkList(L1);
displayLinkList(L1);
return 0;
}
（2）尾插法
- 創(chuàng)建鏈表
//尾插法
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;
}
}
- 輸出結(jié)果
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;
}
- 輸出結(jié)果
int main() {
LinkList L;
createLinkByTail(L);
displayLinkList(L);
int position = 3;
LinkList p= queryByIndex(L, position-1);
printf("\n\t第 %d 個(gè)元素的值是 %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;
}
- 輸出結(jié)果
int main() {
LinkList L;
createLinkByTail(L);
displayLinkList(L);
int positionInsert1 = 3;
printf("\n\t在第 %d 個(gè)位置插入\n", positionInsert1);
LinkList LInsert1 = insertByIndex(L, positionInsert1 - 1, 333);
displayLinkList(LInsert1);
int positionInsert2 = 1;
printf("\n\t在第 %d 個(gè)位置插入\n", positionInsert2);
LinkList LInsert2 = insertByIndex(LInsert1, positionInsert2 - 1, 111);
displayLinkList(LInsert2);
int positionInsert3 = 8;
printf("\n\t在第 %d 個(gè)位置插入\n", positionInsert3);
LinkList LInsert3 = insertByIndex(LInsert2, positionInsert3 - 1, 888);
displayLinkList(LInsert3);
int positionInsert4 = 10;
printf("\n\t在第 %d 個(gè)位置插入\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;
}
- 輸出結(jié)果
int main() {
LinkList L;
createLinkByTail(L);
displayLinkList(L);
int positionDel1 = 3;
printf("\n\t刪除第 %d 個(gè)元素的值\n", positionDel1);
LinkList LDel1= deleteByIndex(L, positionDel1 - 1);
displayLinkList(LDel1);
int positionDel2 = 1;
printf("\n\t刪除第 %d 個(gè)元素的值\n", positionDel2);
LinkList LDel2 = deleteByIndex(LDel1, positionDel2 - 1);
displayLinkList(LDel2);
int positionDel3 = 4;
printf("\n\t刪除第 %d 個(gè)元素的值\n", positionDel3);
LinkList LDel3 = deleteByIndex(LDel2, positionDel3 - 1);
displayLinkList(LDel3);
return 0;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-550121.html
2.5、合并兩個(gè)單鏈表
//合并兩個(gè)單鏈表
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;
}
- 輸出結(jié)果
文章來源地址http://www.zghlxwxcb.cn/news/detail-550121.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) - 線性表（C語言版）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
