5qbaby：数据结构-单链表-C语言实现

1.单链表定义（不带头结点

//二层指针-->改指针的值需要传递指针的地址才能改！！！//不带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode{ int data; struct LNode* next;}LNode,*LinkList;void InitList(LNode** L) { *L == NULL;}void main() { LNode* L;//声明一个指向单链表的指针 InitList(&L);}//不带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode{ int data; struct LNode* next;}LNode,*LinkList;void InitList(LinkList *L) { *L = NULL;}void main() { LinkList L;//声明一个指向单链表的指针 InitList(&L); printf("%p\n", L);}

2.单链表定义（带头结点）

//带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode{ int data; struct LNode* next;}LNode,*LinkList;int InitList(LinkList *L) { *L = (LNode*)malloc(sizeof(LNode)); if (*L == NULL) {//内存不足分配失败 return 0; } (*L)->next = NULL; return 1;}void main() { LinkList L;//声明一个指向单链表的指针 InitList(&L); printf("%p\n", L);}

3.单链表的插入（带头结点）

//带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode{ int data; struct LNode* next;}LNode,*LinkList;//初始化int InitList(LinkList *L) { *L = (LNode*)malloc(sizeof(LNode)); if (*L == NULL) {//内存不足分配失败 return 0; }; (*L)->next = NULL; return 1;}//在第i个位置查入元素e （带头结点） 插入到第i个位置 需要移动i-1次void ListInsert(LinkList *L,int i,int e) { if (i < 1) { return 0; } LNode* p; int j = 0; p = *L; while (p!=NULL && j<i-1) { p = p->next; j++; } if (p == NULL) { return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return 1;}void main() { LinkList L;//声明一个指向单链表的指针 InitList(&L); ListInsert(&L,1,100); printf("%d\n",(*(L->next)).data);//100}

4.单链表的插入（不带头结点）

//不带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;//初始化void InitList(LinkList* L) { *L = NULL;}//在第i个位置查入元素e （带头结点）int ListInsert(LinkList* L, int i, int e) { if (i < 1) { return 0; } if (i == 1) { LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = *L;//S指向的值就是L指向的而第一个值 *L = s; //头指针指向新节点 return 1; } LNode* p; int j = 0;//需要移动 i-2次 p = *L; while (p != NULL && j < i - 2) { p = p->next; j++; } if (p == NULL) { return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return 1;}void main() { LinkList L;//声明一个指向单链表的指针 InitList(&L); ListInsert(&L, 1, 100); printf("%d\n",L->data);//100}

5.结点后插

//结点的后插操作#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;int InsertNextNode(LNode* p,int e) { if (p == NULL) { return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL){ return 0; } s->data = e; s->next = p->next; p->next = s; return 1;}改良单链表插入：//带头结点单链表#include<stdio.h>#include <stdlib.h>typedef struct LNode{ int data; struct LNode* next;}LNode,*LinkList;//初始化int InitList(LinkList *L) { *L = (LNode*)malloc(sizeof(LNode)); if (*L == NULL) {//内存不足分配失败 return 0; }; (*L)->next = NULL; return 1;}//后插int InsertNextNode(LNode* p, int e) { if (p == NULL) { return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) { return 0; } s->data = e; s->next = p->next; p->next = s; return 1;}//在第i个位置查入元素e （带头结点）void ListInsert(LinkList *L,int i,int e) { if (i < 1) { return 0; } LNode* p; int j = 0; p = *L; while (p!=NULL && j<i-1) { p = p->next; j++; } if (p == NULL) { return 0; } InsertNextNode(p,e);//一行代码替代后插操作}void main() { LinkList L;//声明一个指向单链表的指针 InitList(&L); ListInsert(&L,1,100); printf("%d\n",(*(L->next)).data);//100}

6.结点前插

方法一：#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;//前插操作(交换数据)int InsertProiorNode(LNode* p, int e) { if (p == NULL) { return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) { return 0; } s->next = p->next; p->next = s; s->data = p->data; p->data = e; return 1;}方法二：#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;//前插操作(交换数据)int InsertProiorNode(LNode* p, LNode* s) { if (p == NULL) { return 0; } s->next = p->next; p->next = s; int temp = s->data;//交换数据 s->data = p->data; p->data = temp; return 1;}

7.按位序删除（带头结点）

void ListDelete(LinkList* L, int i, int* e) { if (i < 1) { return 0; } LNode* p; int j = 0; p = *L; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return 0; } if (p->next == NULL) {//没有下一个结点 return 0; } LNode* q = p->next; *e = q->data; p->next = q->next; free(q); return 1;}

8.指定结点删除

#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;//指定结点删除（该节点换位后一个节点）int DeleteNode(LNode* p) { if (p != NULL) { return 0; } LNode* q = p->next; p->data = q->data; p->next = q->next; free(q); return 1;}

9.单链表的查找（按位查找）

#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;LNode* getElem(LinkList* L, int i) { if (i < 0) { return 0; } LNode* p; int j = 0; p = *L; while (p != NULL && j < i) { p = p->next; j++; } return p;}

10.单链表的查找（按值查找）

LNode* getElem(LinkList* L, int e) { LNode* p = (*L)->next; while (p != NULL && p->data != e) { p = p->next; } return p;}

11.求表长

int lengtn(LinkList* L) { int len = 0; LNode* p = *L; while (p->next != NULL) { p = p->next; len++; } return len;}

12尾插法

#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;void List_TailInsert(LinkList* L) { int x; *L = (LNode*)malloc(sizeof(LNode)); LNode* s, * r = *L; scanf("%d", &x); while (x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } r->next = NULL;}void main() { LinkList L; List_TailInsert(&L); printf("%d\n", (L->next)->data);}

13.头插法

#include<stdio.h>#include <stdlib.h>typedef struct LNode { int data; struct LNode* next;}LNode, * LinkList;void List_HeadInsert(LinkList* L) { LNode* s; int x; (*L) = (LNode*)malloc(sizeof(LNode)); (*L)->next = NULL; scanf("%d", &x); while (x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; s->next = (*L)->next; (*L)->next = s; scanf("%d", &x); }}void main() { LinkList L; List_HeadInsert(&L); printf("%d\n", (L->next)->data);}

14.链表逆置