數據結構-單鏈表操作及代碼實現（C語言）

（一）單鏈表

與線性表支持隨機訪問的特點相比，單鏈表的特點是適合插入與刪除。

結構體定義

typedef int ElementType; // 數據元素類型定義

typedef struct LNode // 單鏈表結構體定義
{
  ElementType data;   // 數據域
  struct LNode *next; // 存儲下一個結點的地址
} LNode, *LinkedList; // Lnode表示結點；LinkedList = LNode*表示鏈表

（二）單鏈表的主要操作

單鏈表分為帶頭結點和不帶頭結點，這里闡述使用帶頭結點的單鏈表。

1.單鏈表的初始化

初始化一個單鏈表我們首先需要創建一個新結點。
在C語言中，malloc函數可以給我們分配指定長度的內存空間。

LinkedList init_link_list()
{
  LinkedList L = (LinkedList)malloc(sizeof(LNode)); // 創建頭結點
  L->next = NULL;                                   // 將頭結點的指針域置為NULL
  return L;                                         // 返回
}

其他內容請見下方完整代碼...

完整代碼如下：

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

typedef int ElementType; // 數據元素類型定義

typedef struct LNode // 單鏈表結構體定義
{
  ElementType data;   // 數據域
  struct LNode *next; // 存儲下一個結點的地址
} LNode, *LinkedList; // Lnode表示結點；LinkedList = LNode*表示鏈表

// ----------------------------------------------------------------
LinkedList init_link_list();                             // 初始化含頭結點的單鏈表
void iterate_link_list(LNode L);                         // 遍歷單鏈表
void head_insert(LinkedList L, int n);                   // 頭插法建立單鏈表（逆序插入）
void rear_insert(LinkedList L, int n);                   // 尾插法建立單鏈表（順序插入）
void insert_element(LinkedList L, int i, ElementType e); // 在第i個位置插入元素e
void delete_element(LinkedList L, int i);                // 刪除第i個位置的元素e
int get_length(LNode L);                                 // 計算單鏈表的長度
ElementType get_element(LNode L, int i);                 // 查找i位置的元素
int locate_element(LNode L, int value);                  // 查找某個元素的位置

void selection();
// ----------------------------------------------------------------

// ----------------------------------------------------------------

LinkedList init_link_list()
{
  LinkedList L = (LinkedList)malloc(sizeof(LNode)); // 創建頭結點
  L->next = NULL;                                   // 將頭結點的指針域置為NULL
  return L;                                         // 返回
}

void iterate_link_list(LNode L)
{
  LinkedList p = L.next; // p結點指向第一個元素
  while (p)              // 當 p->next != NULL時，進行遍歷訪問
  {
    printf("%d ", p->data); // 打印元素值
    p = p->next;            // p指針向后移動
  }
  printf("\n");
  free(p); // 釋放p結點
}

void head_insert(LinkedList L, int n)
{
  for (int i = n; i > 0; i--)
  {
    LinkedList p = (LinkedList)malloc(sizeof(LNode)); // 生成新結點
    scanf(" %d", &p->data);                           // 輸入元素值
    p->next = L->next;                                //
    L->next = p;                                      // 插入到表頭
  }
}

void rear_insert(LinkedList L, int n)
{
  LinkedList r = L;           // r結點指向頭結點
  for (int i = n; i > 0; i--) // 循環插入
  {
    LinkedList p = (LinkedList)malloc(sizeof(LNode)); // 生成新結點
    scanf(" %d", &p->data);                           // 輸入元素值
    p->next = NULL;                                   // 新結點的next指針域置為NULL
    r->next = p;                                      // 插入到表尾
    r = r->next;                                      // 表尾元素后移
  }
}

void insert_element(LinkedList L, int i, ElementType e)
{
  int j = 0;        // 當前是第0個元素，即頭結點
  LinkedList p = L; // p結點指向頭結點
  while (p)
  {
    if (j == i - 1) // 找到了i-1位置
    {
      LinkedList temp = (LinkedList)malloc(sizeof(LNode)); // 創建新結點
      temp->data = e;                                      // 將元素e賦值給temp的數據域
      temp->next = p->next;                                // 新插入的結點temp指向p結點的下一個結點
      p->next = temp;                                      // 將p的下一個結點指向新插入的結點temp
      return;
    }
    j++;         // j++
    p = p->next; // p指針向后移動
  }
}

void delete_element(LinkedList L, int i)
{
  int j = 0;           // 當前是第0個元素
  LinkedList p = L;    // p結點指向頭結點
  while (p && p->next) // 新加入了p->next!=NULL的判斷？ 為了防止刪除最后一個元素時(p->next==NULL)進入循環
  {
    if (j == i - 1) // 找到了i-1位置
    {
      // 將當前結點后的元素刪除
      LinkedList r = p->next; // 記錄p結點的下一個結點
      p->next = r->next;      // p->next =  p->next->next
      free(r);                // 釋放r結點
      return;
    }
    j++;         // j++
    p = p->next; // p指針向后移動
  }
}

int get_length(LNode L)
{
  LinkedList p = L.next; // p指向第一個元素
  int length = 0;
  while (p) // 當p->next != NULL時
  {
    length++;    // 長度加1
    p = p->next; // p指針向后移動
  }
  return length; // 返回鏈表長度
}

ElementType get_element(LNode L, int i)
{
  int j = 1;             // 當前是第幾個元素
  LinkedList p = L.next; // p結點指向存放第一個元素的結點
  while (p)              // 當p->next != NULL時
  {
    if (j == i)       // 當前位置j是否等于i位置
      return p->data; // 返回元素值
    j++;              // j++
    p = p->next;      // p指針向后移動
  }
  exit(0); // 退出
}

int locate_element(LNode L, int value)
{
  int j = 1;             // 當前是第幾個元素
  LinkedList p = L.next; // p結點指向存放第一個元素的結點
  while (p)              // 當p->next != NULL時
  {
    if (p->data == value) // 找到了
      return j;           // 返回
    j++;                  // j++
    p = p->next;          // p指針向后移動
  }
  return -1; // 未找到
}

// ----------------------------------------------------------------

void selection()
{

  int option = 0;         // 當前選項
  LinkedList L = NULL;    // 初始化
  int n = 0;              // 插入元素個數
  int insertPosition = 0; // 插入元素的位置
  int insertElement = 0;  // 插入的元素
  int deletePosition = 0; // 刪除的元素位置
  int locatePosition = 0; // 查找的第i個位置
  int findElement = 0;    // 查找的元素

  while (1)
  {
    printf("========================================================================\n");

    printf("\t\t 1. Init Single LinkedList. \t\t\n");                   // 初始化帶頭結點的單鏈表
    printf("\t\t 2. Insert Element(head insert). \t\t\n");              // 頭插法建立單鏈表
    printf("\t\t 3. Insert Element(rear insert). \t\t\n");              // 尾插法建立單鏈表
    printf("\t\t 4. Delete element at position i. \t\t\n");             // 刪除第i個位置的元素e
    printf("\t\t 5. Insert an Element at position i. \t\t\n");          // 在第i個位置插入元素e
    printf("\t\t 6. Find the element at position i. \t\t\n");           // 查找i位置的元素
    printf("\t\t 7. Find the location of a specified element. \t\t\n"); // 查找某個指定元素的位置
    printf("\t\t 8. Current length of the Single LinkedList. \t\t\n");  // 獲取單鏈表長度
    printf("\t\t 9. Print Element. \t\t\n");                            // 打印元素
    printf("\t\t 10. Exit. \t\t\n");                                    // 退出

    printf("========================================================================\n");
    printf("Input one number in(1-9): ");
    scanf("%d", &option);
    switch (option)
    {
    case 1:
      L = init_link_list();
      printf("~_~ LinkList successfully initialized.\n");
      break;
    case 2:
      printf("Please enter the number of inserted elements(eg: 10): ");
      scanf("%d", &n);
      head_insert(L, n);
      printf("~_~ Head Insert LinkList successfully.\n");
      break;
    case 3:
      printf("Please enter the number of inserted elements(eg: 10): ");
      scanf("%d", &n);
      rear_insert(L, n);
      printf("~_~ Rear Insert LinkList successfully.\n");
      break;
    case 4:
      printf("Input delete position i (eg: 2): ");
      scanf("%d", &deletePosition);
      delete_element(L, deletePosition);
      break;
    case 5:
      printf("Input insert position i (eg: 2 66): ");
      scanf("%d %d", &insertPosition, &insertElement);
      insert_element(L, insertPosition, insertElement);
      break;
    case 6:
      printf("Input insert position i and element e (eg: 2): ");
      scanf("%d", &locatePosition);
      printf("~_~ The position [%d] element is: %d \n", locatePosition, get_element(*L, locatePosition));
      break;
    case 7:
      printf("Input the element e (eg: 33): ");
      scanf("%d", &findElement);
      printf("~_~ The element [%d] position is: %d \n", findElement, locate_element(*L, findElement));
      break;
    case 8:
      printf("~_~ Current single list length: %d\n", get_length(*L));
      break;
    case 9:
      printf("~_~ Start Iterate LinkList.\n");
      iterate_link_list(*L);
      printf("~_~ Iterate LinkList successfully.\n");
      break;
    case 10:
      printf("~_~ Exit successfully.\n");
      return;
    default:
      printf("~_~ Please enter the correct serial number!\n ");
      break;
    }
  }
}

int main()
{

  // LinkedList L = init_link_list();
  // // head_insert(L, 9); // 頭插法
  // rear_insert(L, 9); // 尾插法
  // printf("current single list length: %d\n", get_length(*L));
  // iterate_link_list(*L);

  // int i = 0, element = 0;
  // printf("input insert position i and element e.(eg: 2 99):");
  // scanf("%d %d", &i, &element);
  // insert_element(L, i, element);
  // printf("current single list length: %d\n", get_length(*L));
  // iterate_link_list(*L);

  // delete_element(L, 3); // 刪除第2個位置的元素
  // printf("current single list length: %d\n", get_length(*L));
  // iterate_link_list(*L);

  selection();
  return 0;
}

posted @ 2024-06-02 23:33 Hui_Li 閱讀(1954) 評論(1) 收藏舉報

刷新頁面返回頂部

Hui Li