程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 使用C語言實現線性表

使用C語言實現線性表

編輯:關於C語言

使用C語言實現線性表


線性表是最常用且最簡單的一種數據結構。一個線性表是n個數據元素的有限序列,序列中的每個數據元素,可以是一個數字,可以是一個字符,也可以是復雜的結構體或對象。例如:1,2,3,4,5是一個線性表,A,B,C,D...Z是一個線性表,一列列車的車廂1,車廂2...車廂n是一個線性表。   線性表的機內表示法(又稱存儲結構)有2種,一種是順序存儲結構,另一種是鏈式存儲結構。   順序存儲結構,顧名思義就是按順序來存儲的一種存儲結構,比如線性表(1,2,3,4,5),共計5個元素, 每個int型的數據元素假設占用4個存儲單元,假設第1個元素數字1的存儲地址是1000,則第2個元素數字2的存儲地址是1004,第3個元素數字3的存儲地址是1008,依此類推,第n個數據元素的存儲地址是LOC(an) = LOC(a1)+(n-1)k.(k表示每個數據元素占用的存儲單元的長度) 顯而易見,這種存儲結構,相鄰元素在物理位置上也相鄰。 通常,我們把采用這種存儲結構的線性表稱為“順序表”。   鏈式存儲結構,它不要求相鄰的元素在物理位置上也相鄰,所以它可用一組處在任意位置的存儲單元來存儲線性表的數據元素。既然這樣,那應該怎樣表示數據元素之間的邏輯關系呢? 為了表示數據元素之間的邏輯關系,對於數據元素a1來說,除了存儲其自身的信息之外,還需要存儲一個指示其直接後繼的信息,所以我們引入指針的概念:稱存儲數據元素信息的域稱為數據域,而存儲直接後繼地址信息的域稱為指針域。 我們形象地稱這種即包含自身數據信息,又包含其直接後繼地址信息的數據元素為“結點”。 顯而易見,這種存儲結構,相鄰元素在物理位置上不一定相鄰,他們之間用指針來表示邏輯關系。 通常,我們把采用這種存儲結構的線性表稱為“線性鏈表”。   有了基本的概念之後,我們就可以使用編程語言進行描述,使用C、C++、C#、Java等都可以,這篇文章我使用C語言描述。   一、順序表 為了描述順序表,我們首先要聲明一個結構,如下:   #define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量 #define LISTINCREMENT 10   //線性表存儲空間的分配增量(當存儲空間不夠時要用到) typedef int ElemType;      //數據元素的類型,假設是int型的 typedef struct{     ElemType *elem;       //存儲空間的基地址     int length;      //當前線性表的長度     int listsize;    //當前分配的存儲容量 }SqList; 定義好線性表後,就可以對它進行操作了,常見的線性表的基本操作有:創建線性表、查找元素、插入元素、刪除元素、清空、歸並等。 線性表的基本操作在順序表中的實現: 1.創建線性表   int InitList(SqList &L) {     L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//開辟一個存儲空間,並把這塊存儲空間的基地址賦值給elem     if (!L.elem)     {         return -1; //空間分配失敗     }          L.length = 0; //當前長度     L.listsize = LIST_INIT_SIZE; //當前分配量     return 0; } 2.查找元素(按值查找) 線性表的按值查找是指在線性表中查找與給定值x相等的數據元素。完成該操作最簡單的方法是從第一個元素a1開始依次和x比較,若相等,則返回該元素的下標。 若查遍整個表都沒有找到與x相等的元素,則返回-1。 時間復雜度:算法的基本操作(比較x與L中第i<1,n>個元素)與元素x在表中的位置有關,也與表長有關。當a1=x時,比較1次成功,當an=x時,比較n次成功,平均比較次數為n+1/2,時間復雜度為O(n)。   int LocateElem(SqList L, ElemType x) {     int pos = -1;     for (int i = 0; i < L.length; i++)     {         if (L.elem[i] == x)         {             pos = i;         }     }     return pos; } 3.插入元素 時間復雜度O(L.length)即O(n)   int ListInsert(SqList &L, int i, ElemType e) {     //判斷插入位置的合法性     if (i<1 || i>L.length+1) return -1;      //判斷存儲空間是否夠用     if (L.length >= L.listsize)     {         ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));         if (!newbase) return -1;//存儲空間分配失敗         L.elem = newbase;//新基址         L.listsize += LISTINCREMENT;//增加存儲容量     }     //插入操作     ElemType *q, *p; //定義2個指針變量     q = &(L.elem[i-1]); //q為插入位置(注意形參i是序號,序號是從從1開始的,而下標是從0開始的,因此這裡轉成下標後是i-1)     for (p = &(L.elem[L.length - 1]); p >= q; --p) //從ai到an-1依次後移,注意後移操作要從後往前進行     {         *(p + 1) = *p;     }     *q = e;     ++L.length;//表長加1     return 0; } 4.刪除元素 時間復雜度O(L.length)即O(n)   int ListDelete(SqList &L, int i, ElemType &e) {     //判斷刪除位置的合法性     if (i<1 || i>L.length) return -1;      //刪除操作     ElemType *q, *p;//定義2個指針變量      p = &(L.elem[i - 1]);//p為被刪除元素的位置(注意形參i是序號,序號是從從1開始的,而下標是從0開始的,因此這裡轉成下標後是i-1)     e = *p; //被刪除的元素賦值給e(可能用不到,也可能用到,所以保存給e吧)     q = L.elem + L.length - 1;//q指向表尾最後一個元素(q是最後一個元素的地址)     for (++p; p <= q; ++p) //從p的下一個元素開始依次前移     {         *(p - 1) = *p;     }          --L.length;//表長減1     return 0; } 測試代碼如下:   #include <stdio.h> #include <stdlib.h> int main() {     SqList list;     InitList(list);       int n = 10;          //添加10個數字給線性表list     for (int i = 0; i < 10; i++)     {         ListInsert(list, i+1, i+1);     }     //刪除第5個     ElemType e;     ListDelete(list, 5, e);     printf("刪除的元素是:%d\n", e);       //在第2個位置插入一個元素-1     ListInsert(list, 2, -1);          //輸出線性表     for (int i = 0; i < 10; i++)     {         printf("%d ", list.elem[i]);     }     //輸出結果是:1 -1 2 3 4 6 7 8 9 10       system("pause"); } 二、線性鏈表 為了描述線性鏈表,我們首先要聲明一個結構,如下:   typedef struct LNode{     ElemType data; //數據域     struct LNode *next;//指針域 }LNode; 定義好線性鏈表後,就可以對它進行操作了,常見的線性鏈表的基本操作有:查找、插入、刪除、清空等。 線性表的基本操作在線性鏈表中的實現: 1.1創建鏈表(頭插法) 時間復雜度O(n)   LNode * CreateListHead(int n) {     LNode *L;     L = (LNode *)malloc(sizeof(LNode));     L->next = NULL;     LNode *p;//p為新結點,指向最後一個元素     for (int i = n; i > 0; --i)     {         p = (LNode *)malloc(sizeof(LNode));//為新結點開辟空間         scanf("%d",&p->data);         p->next = L->next;         L->next = p;     }     return L; } 1.2創建鏈表(尾插法)   LNode * CreateListTail() {     LNode *L;     L = (LNode *)malloc(sizeof(LNode));     L->next = NULL;//空表     LNode *s, *r = L;//r是尾指針 s是新結點     int x;     scanf("%d", &x);     int flag = 0;//結束標記     while (x != flag)     {         s = (LNode *)malloc(sizeof(LNode));         s->data = x;         r->next = s;         r = s;         scanf("%d", &x);     }     r->next = NULL;//最後一個元素next域指向NULL     return L; } 2.查找元素(取第i個元素)   int GetElem(LNode L, int i, ElemType &e) {     LNode *head,*p;//head是頭指針,p為查找下標     head = &L;     p = head;//p的初值指向第1個元素     int j = 0;     while (p !=NULL && j<i)     {         p = p->next;         j++;     }     if (p == NULL || j>i) return -1; //第i個元素不存在     e = p->data;     return 0; } 3.插入元素 在鏈表中插入結點,只需要修改指針。 若要在第i個結點之前插入元素,則首先需要找到第i-1個結點,然後修改第i-1個結點的指針。 時間復雜度O(n)   int ListInsert(LNode *L, int i, ElemType e) {     LNode *p;//設p為第i-1個結點     //首先要找到第i-1個結點     int j = 0;     p = L;     while (p != NULL && j < i-1)     {         p = p->next;         j++;     }     //申請一個新結點     LNode *s = (LNode *)malloc(sizeof(LNode));     s->data = e;       s->next = p->next; //s的直接後繼指向p原來的直接後繼     p->next = s; //p的直接後繼指向s       return 0; } 4.刪除元素 若要刪除第i個結點,則只需要修改第i-1個結點的指針指向第i+1個即可 時間復雜度O(L.length)即O(n)   int ListDelete(LNode *L, int i, ElemType &e) {     LNode *p,*q;//設p為第i-1個結點 q標示刪除位置     //首先要找到第i-1個結點     int j = 0;     p = L;//p為L的基地址     while (p != NULL && j < i-1)     {         p = p->next;         j++;     }     q = p->next;     p->next = q->next;//p的next域指向p->next->next       e = q->data;     return 0; } 測試代碼如下:   #include <stdio.h> #include <stdlib.h> int main() {     LNode *L;     L = CreateListTail();//創建一個線性鏈表,輸入0結束     ListInsert(L, 1, 100);//在第1個位置插入100     ElemType e;//待刪除的元素     ListDelete(L, 3, e);//刪除第3個元素     LNode *p;     p = L;          printf("輸出線性鏈表:\n");     while (p->next != NULL)     {         p = p->next;         printf("%d ", p->data);     }       system("pause"); }  筆者初學數據結構,如有不足之處,歡迎指正。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved