数据结构---线性表之单链表（C语言）

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #define maxSize 100 /***************单链表结点定义******************/ typedef struct LNode { int data; //data中存放结点数据域 struct LNode *next; //指向后继结点的指针 }LinkList; //单链表结点类型 /*********************输入数据存入数组a********************/ int n; //定义成全局变量,n是输入数据的个数 int a[maxSize]; //这两个只有定义成全局变量才可以在所有的函数中使用！ LinkList *head; LinkList *L; void InData( ) { printf("请输入您要存入数据的个数:"); scanf_s("%d", &n); if (n >= 0 && n < maxSize) { printf("请输入数据："); for (int i = 0; i < n; i++) { scanf_s("%d", &a[i]); } printf("您所输入的数据为："); for (int j = 0; j < n; j++) { printf("%d ", a[j]); } } else { printf("不在区间内！请重新选定数值！"); } } /******************尾插法创建一个链表L（含头结点）**********************/ int CreateList1(LinkList *L) { InData(); LinkList *s,*r; //s用来指向新申请的结点，r用来指向链表L的终端结点 L = (LinkList*)malloc(sizeof(LinkList)); //申请L的头结点空间 head = (LinkList*)malloc(sizeof(LinkList)); L->next = NULL; //初始化 r = L; //r指向头结点，此时的头结点就是终端结点 head = L; //非常重要！！！得到链表的头指针，以便在之后的函数中找到链表调用 for (int i = 0; i <n; i++) { s = (LinkList*)malloc(sizeof(LinkList)); //s指向新申请的结点 s->data = a[i]; r->next = s; //用r来接纳新结点 r = r->next; //r指向终端结点，以便于接纳下一个结点的到来 } r->next = NULL; //数组a中所有的元素都已经装入链表L中，L的终端结点指针域设置为NULL，L就建立完成了 printf("\n链表中的数据为："); LinkList *p = L->next; for (int j = 0; j < n; j++) { printf("%d ",p->data); p = p->next; } return L; } /***********************头插法建立单链表*************************/ void CreateList2(LinkList *L) { InData(); LinkList *s; int i; L = (LinkList*)malloc(sizeof(LinkList)); L->next = NULL; head = (LinkList*)malloc(sizeof(LinkList)); head = L; for (i = 0; i < n; i++) { s= (LinkList*)malloc(sizeof(LinkList)); s->data = a[i]; s->next = L->next; //s所指向的新节点的指针域指向L的开始结点 L->next = s; //头结点的指针域指向s结点，使得s成为新的开始结点 } printf("\n链表中的数据为："); LinkList *p = L->next; for (int j = 0; j < n; j++) { printf("%d ", p->data); p = p->next; } return L; } /********************在指定位置后插入数据****************/ int InsertNode() { LinkList *s,*r; s = (LinkList*)malloc(sizeof(LinkList)); r = (LinkList*)malloc(sizeof(LinkList)); r = head; //r此时和头指针一样指向链表的头结点处 int x, e; printf("\n请输入您想插入数据的位置："); scanf_s("%d", &x); if (x<0 || x>n) { printf("\n区间错误"); } else { printf("\n请输入数据："); scanf_s("%d", &e); s->data = e; } for (int i = 0; i < x; i++) head = head->next; s->next = head->next; //插入最关键的两步 head->next = s; n++; //链表长度增加 printf("\n数据为："); for (int j = 0; j < n; j++) { r = r->next; printf("%d ", r->data); } return L; } /*********************删除某个位置的结点*****************/ int DeleteNode() { LinkList *q,*p; int x; q = (LinkList*)malloc(sizeof(LinkList)); p = (LinkList*)malloc(sizeof(LinkList)); p = head; printf("\n请输入您想删除的结点的位置："); scanf_s("%d", &x); if (x<0 || x>n) { printf("不在区间内！"); } for (int i = 0; i < x; i++) { head = head->next; } q = head->next; head->next = q->next; n--; free(q); printf("\n数据为："); for (int j = 0; j < n; j++) { p = p->next; printf("%d ", p->data); } return L; } void main() { CreateList1(&L); //InsertNode(); DeleteNode(); system("pause"); }