代碼參考《妙趣橫生的算法.C語(yǔ)言實(shí)現(xiàn)》

文章目錄

• 前言
• • 1、創(chuàng)建順序表
  • 2、順序表插入元素
  • 3、順序表刪除元素
  • 4、順序表實(shí)例分析
  • • 1、靜態(tài)
    • 2、動(dòng)態(tài)
  • 5、順序表總結(jié)

---

前言

本章總結(jié)：從靜態(tài)和動(dòng)態(tài)分別進(jìn)行順序表的創(chuàng)建、插入、刪除、以及實(shí)例分析

---

1、創(chuàng)建順序表

1、靜態(tài)地生成一張順序表

#define MaxSize=100; ElemType Sqlist[MaxSize]; int len; //len表示順序表的長(zhǎng)度

2、動(dòng)態(tài)地生成一張順序表

#define MaxSize 10typedef int ElemType; typedef struct{int *elem; //指向順序表首地址elemint length; //順序表中表的長(zhǎng)度(元素個(gè)數(shù))int listsize; //順序表的存儲(chǔ)空間容量 }Sqlist; void initSqlist(Sqlist* L) {L->elem = (int*)malloc(MaxSize*sizeof(ElemType)); //開辟內(nèi)存，并將該段空間首地址賦值給L->elemif (!L->elem){printf("分配內(nèi)存失敗");exit(0);} //如果分配內(nèi)存失敗，返回L->length = 0; //生成一張空的順序表L->listsize = MaxSize; }

靜態(tài)定義，表占用的內(nèi)存空間開辟在內(nèi)存的靜態(tài)區(qū)，也就是函數(shù)棧上，該區(qū)域的從內(nèi)存空間會(huì)隨著函數(shù)調(diào)用的完成而被系統(tǒng)自動(dòng)回收。動(dòng)態(tài)生成一個(gè)順序表，內(nèi)存空間開辟在內(nèi)存的動(dòng)態(tài)區(qū)上，也就是堆內(nèi)存上，這個(gè)區(qū)域的內(nèi)存空間不會(huì)被系統(tǒng)自動(dòng)回收，需要程序主動(dòng)釋放.

2、順序表插入元素

在長(zhǎng)度為n的順序表中的第i個(gè)位置插入新元素item

1、靜態(tài)表

void InsertElem(ElemType Sqlist[],int &n,int i,ElemType item) {//向順表中Sqlist中第i個(gè)位置插入元素item,順序表原長(zhǎng)為nint t;if(n==MaxSize || i<1 ||i>n+1) exit(0); //非法插入：判斷插入元素的位置是否對(duì)，或者表是否已滿，因?yàn)楸淼膬?nèi)存大小是固定不變的。for(t=n-1;t>=i-1;t--) Sqlist[t+1]=Sqlist[t]; //將i-1后的元素往后移動(dòng)一個(gè)元素Sqlist[i-1]=item; //在i位置上插入元素itemn=n+1; //數(shù)組長(zhǎng)度+1 }

2、動(dòng)態(tài)表,如果順序表已滿，可以追加一段內(nèi)存空間

void InsertElem(Sqlist* L, int i, ElemType item) {//向順序表L中第i個(gè)位置插入元素itemElemType* base, * insertPtr, * p;if (i<1 || i>L->length + 1){printf("非法插入");exit(0);} //非法插入if (L->length >= L->listsize){base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));//重新追加空間L->elem = base; //更新內(nèi)存基地址L->listsize = L->listsize + 100; //存儲(chǔ)空間增大100單元}insertPtr = &(L->elem[i - 1]); //insertPtr為插入位置for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)*(p + 1) = *p; //將i-1以后的元素順序往后移動(dòng)一個(gè)元素位置*insertPtr = item; //在第i個(gè)位置插入元素L->length++; }

3、順序表刪除元素

刪除第i個(gè)位置元素的方法：將第i個(gè)位置以后的元素依次前移，從而覆蓋掉第i個(gè)元素

1、靜態(tài)表

void DelElem(ElemType Sqlist[],int &n,int i) {int j;if(i<1 || i>n) exit(0); //非法刪除、for(j=i;j<n;j++)Sqlist[j-1]=Sqlist[j];//將第i個(gè)位置以后的元素依次前移n--; //表長(zhǎng)-1 }

2、動(dòng)態(tài)表

void DelElem(Sqlist* L, int i) {ElemType* delItem, * q;if (i<1 || i>L->length){printf("非法刪除");exit(0);}delItem = &(L->elem[i - 1]); //delItem指向表中第i個(gè)元素q = L->elem + L->length - 1; //q指向表尾for (++delItem;delItem <= q;++delItem)*(delItem - 1) = *delItem; //將第i位置以后的元素依次前移L->length--; //表長(zhǎng)-1 }

4、順序表實(shí)例分析

1、靜態(tài)

題目要求：
創(chuàng)建一個(gè)靜態(tài)的順序表存放整數(shù)，大小為10，完成以下操作：
1、輸入6個(gè)整數(shù)，打印出順序表中的內(nèi)容，并顯示表中剩余的空間個(gè)數(shù)
2、在順序表中第3個(gè)位置插入元素0，打印出順序表中的內(nèi)容，并顯示表中剩余的空間個(gè)數(shù)
3、試圖向表中第11個(gè)位置插入整數(shù)0，程序提示超出范圍
4、刪除表中的第6個(gè)元素，打印出順序表中的內(nèi)容，并顯示表中剩余的空間個(gè)數(shù)

#include "stdio.h" #define MaxSize 10//基本操作// //向順序表中插入元素 Sqlist:表首地址 *len:表的長(zhǎng)度 i:待插入元素的位置 x:待插入元素的元素值 void insertElem(int Sqlist[], int* len, int i, int x) {int t;if (i<1 || i> * len + 1 || *len == MaxSize) //非法插入操作，或者數(shù)組元素已滿{printf("This insert is illegal\n");return;}for (t = *len - 1;t >= i - 1;t--)Sqlist[t + 1] = Sqlist[t];Sqlist[i - 1] = x; //插入元素*len = *len + 1; } //向順序表中刪除元素 Sqlist:表首地址 *len:表的長(zhǎng)度 i:插入元素的位置 void DelElem(int Sqlist[], int* len, int i) {int j;if (i<1 || i>*len){printf("This insert is illgel\n");return;}for (j = i;j <= *len - 1;j++)Sqlist[j - 1] = Sqlist[j];*len = *len - 1; } void show_sqlist(int Sqlist[],int len) {int i = 0;for (i = 0;i < len;i++)printf("%d", Sqlist[i]); } //測(cè)試函數(shù) int main() {int Sqlist[MaxSize]; //定義一個(gè)靜態(tài)順序表int len=0;int i;printf("please input six interger number\n");for (i = 0;i < 6;i++){scanf("%d", &Sqlist[i]);len++;}show_sqlist(Sqlist, len);printf("\nthe spare length is %d\n", MaxSize - len);insertElem(Sqlist, &len, 3, 0);show_sqlist(Sqlist, len);insertElem(Sqlist, &len, 11, 0); //在表中第11位置插入整數(shù)0DelElem(Sqlist, &len, 6);show_sqlist(Sqlist, len);printf("\nthe spare length is %d\n", MaxSize - len);return 0; }

result：

2、動(dòng)態(tài)

編寫一個(gè)程序，動(dòng)態(tài)的創(chuàng)建一個(gè)順序表。
要求：
1、順序表初始長(zhǎng)度為10，向順序表中輸入15個(gè)整數(shù)，并打印出來(lái)
2、再刪除順序表中的第五個(gè)元素，打印出刪除后的結(jié)果

/* 編寫一個(gè)程序，動(dòng)態(tài)的創(chuàng)建一個(gè)順序表。 要求： 1、順序表初始長(zhǎng)度為10，向順序表中輸入15個(gè)整數(shù)，并打印出來(lái) 2、再刪除順序表中的第五個(gè)元素，打印出刪除后的結(jié)果 */ #include "stdio.h" #include "conio.h" #include "malloc.h" #include <stdlib.h> #define MaxSize 10typedef int ElemType; typedef struct{int *elem; //指向順序表首地址elemint length; //順序表中表的長(zhǎng)度(元素個(gè)數(shù))int listsize; //順序表的存儲(chǔ)空間容量 }Sqlist;//初始化一個(gè)順序表 void initSqlist(Sqlist* L) {L->elem = (int*)malloc(MaxSize*sizeof(ElemType)); //開辟內(nèi)存，并將該段空間首地址賦值給L->elemif (!L->elem){printf("分配內(nèi)存失敗");exit(0);} //如果分配內(nèi)存失敗，返回L->length = 0; //生成一張空的順序表L->listsize = MaxSize; } /* L：Sqlist類型指針 i：插入元素的位置 item:插入的元素 */ void InsertElem(Sqlist* L, int i, ElemType item) {//向順序表L中第i個(gè)位置插入元素itemElemType* base, * insertPtr, * p;if (i<1 || i>L->length + 1){printf("非法插入");exit(0);} //非法插入if (L->length >= L->listsize){base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));//重新追加空間L->elem = base; //更新內(nèi)存基地址L->listsize = L->listsize + 100; //存儲(chǔ)空間增大100單元}insertPtr = &(L->elem[i - 1]); //insertPtr為插入位置for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)*(p + 1) = *p; //將i-1以后的元素順序往后移動(dòng)一個(gè)元素位置*insertPtr = item; //在第i個(gè)位置插入元素L->length++; } /* L：Sqlist類型指針 i：刪除元素的位置 */ void DelElem(Sqlist* L, int i) {ElemType* delItem, * q;if (i<1 || i>L->length){printf("非法刪除");exit(0);}delItem = &(L->elem[i - 1]); //delItem指向表中第i個(gè)元素q = L->elem + L->length - 1; //q指向表尾for (++delItem;delItem <= q;++delItem)*(delItem - 1) = *delItem; //將第i位置以后的元素依次前移L->length--; //表長(zhǎng)-1 } void print_list(Sqlist *L) {int i = 0;for (i = 0;i < L->length;i++)printf("%d ",L->elem[i]); } //測(cè)試函數(shù) int main() {Sqlist L;int i = 0;initSqlist(&L);for (i = 0;i < 15;i++)InsertElem(&L,i+1,i+1); //每次在末尾插入一個(gè)元素printf("\n the content of list is \n");print_list(&L);DelElem(&L, 5);printf("\n the content of list after delete is \n");print_list(&L);_getche();return 0; }

5、順序表總結(jié)

線性表的優(yōu)點(diǎn)：構(gòu)造簡(jiǎn)單、操作方便，通過(guò)順序表的首地址(數(shù)組名)可直接對(duì)表進(jìn)行隨機(jī)存取，從而存取速度快，系統(tǒng)開銷小。
缺點(diǎn)：有可能浪費(fèi)存儲(chǔ)空間，在插入或刪除一個(gè)元素時(shí)，需要對(duì)插入或刪除位置后面的所有元素逐個(gè)進(jìn)行移動(dòng)，從而導(dǎo)致操作效率較低。
所以順序表適用于表的長(zhǎng)度不經(jīng)常發(fā)生變化的場(chǎng)合，如批處理

總結(jié)

以上是生活随笔為你收集整理的【数据结构基础笔记】【顺序表】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。