FDS（N）：单链表

实现维护一个单链表

单链表

线性表：1. 有限的序列。 2. 序列中每一个元素都有唯一的前驱和后续，除了开头和结尾两个节点

链表：内存是不连续的，元素会各自被分配一块内存，内存和内存之间用指针相连

单链表操作

增加

1 头插法

新建一个节点，新元素next指向head元素

2 尾插法

新建一个节点，tail元素next指向新元素

删除

选出待删除的节点，使其前一个节点的next指向后一个节点

删除该节点

代码实现维护一个链表：

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

void clearScreen() {
    system("cls");
}
int len = 0;
typedef struct Node
{
  int data;
  struct Node *next;
}Node;
Node* CreatList(int len);
Node* DeleteNode(Node* list,int n);
Node* AddList(Node* list,int n,int data);
void ShowList(Node* list);
void FreeList(Node* list);
void displayMenu() {
    printf("========== linkedlist program ==========\n");
    printf("1. Show list\n");
    printf("2. Add list\n");
    printf("3. Remove node\n");
    printf("0. Exit\n");
    printf("====================================\n");
    printf("Select an option: ");
}
int main()
{

  printf("please enter the lenth of the list\n");
  scanf("%d",&len);
  if(len>0)
  {
    Node* list;
    list = CreatList(len);
    ShowList(list);
    int pos,data;
    int choice;
      do
      {
        clearScreen();
        displayMenu();
        scanf("%d", &choice);
        clearScreen();
        switch (choice) {
            case 1:
                ShowList(list);
                break;
            case 2:
                ShowList(list);
                printf("please enter the position that you want to add:\n");
                scanf("%d",&pos);
                printf("please enter the number you want to add :\n");
                scanf("%d",&data);
                list = AddList(list,pos,data);
                ShowList(list);
                break;
            case 3:
                ShowList(list);
                printf("please enter the position that you want to delete:\n");
                scanf("%d",&pos);
                list = DeleteNode(list,pos);
                ShowList(list);
                break;
            case 0:
                free(list);
                break;
            default:
                printf("Invalid option! Please choose again.\n");
        }
      system("pause");
      } while (choice!=0);

    return 0;
  }
}
Node* CreatList(int len)
{
  Node *head;
  head = (Node*)malloc(sizeof(Node));
  if (!head)
  {
    printf("fail to apply the Memory");
    exit(1);
  }
  head->next = NULL; 
  int i = 0;
  while (i<len)
  {
    Node *l;
    l = (Node*)malloc(sizeof(Node));
    scanf("%d",&(l->data));
    l->next = head->next;
    head->next = l;
    i++;
  }
  return head;
}
void ShowList(Node* list)
{
  printf("the list now is:");
  Node* p;
  p = list->next;
  while(p){
    printf("%d ",p->data);
    p = p->next;
  }
  printf("\n");
  printf("lenth = %d",len);
  printf("\n");
}
void FreeList(Node* list)
{
  while(list)
  {
      Node* temp;
      temp = list;
      list = list->next;
      free(temp);
  }
}
Node* AddList(Node* list,int n,int data)
{
  if(len==0)
  {
    Node* t;
    t = (Node*)malloc(sizeof(Node));
    t->data = data;
    t->next = NULL;
    list->next = t;
    len++;
    return list;
  }
  if (n>len+1)
  {
    printf("beyond the limit\n");
    return list;
  }
  if (n<=0)
  {
    printf("beyond the limit\n");
    return list;
  }
  Node* a;
  a = (Node*)malloc(sizeof(Node));
  a->data = data;
  Node *p;
  p =list;
  int i;
  for ( i = 1; i < n; i++)
  {
    p = p->next;   
  }
  a->next = p->next;
  p->next = a;
  len++;
  return list;
}
Node* DeleteNode(Node* list,int n)
{
  if(len==0)
  {
    printf("the list is empty");
  }
  if (n>len)
  {
    printf("beyond the limit\n");
    return list;
  }
  if (n<=0)
  {
    printf("beyond the limit\n");
    return list;
  }
  Node *p;
  p = list;
  int i;
  for ( i = 1; i < n; i++)
  {
    p = p->next;                                                                          
  }
  Node *temp;
  temp = p->next;
  p->next = temp->next;
  free(temp); 
  len--;
  return list; 
}

它还有非常美丽的GUI哦

Abstract Data Type

Data Type = {Objects}$\cup${operations }

学生选课：十字链表（稀疏矩阵）

Cursor implementation of linked lists（no pointed）