- 特点
- 存在唯一一个称为“第一个”的元素
- 存在唯一一个称为“最后一个”的元素；
- 除第一个元素外，序列中的每个元素只有一个直接前驱
- 除最后一个元素外，序列中的每个元素只有一个直接后继
- 数据元素的类型都是相同的
顺序表操作
- SeqList.h
#ifndef __SEQLIST_H__ #define __SEQLIST_H__#define MAXSIZE 128 typedef int datatype; typedef struct {datatype data[MAXSIZE]; // 从下标1开始，即可以存放的位置：1~MAXSIZE-1int len; }SeqList;// 顺序表的初始化 SeqList* Init_SeqList(); // 顺序表的创建 void CreateSeqList(SeqList* L); // 顺序表的插入 void Insert_SeqList(SeqList* L, int i, datatype x); // 顺序表的打印 void print_SeqList(SeqList* L); // 顺序表的删除 void Delete_SeqList(SeqList* L, int i); //顺序表查找 int Location_SeqList(SeqList* L, datatype x); #endif // !1 - SeqList.c
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include"SeqList.h"SeqList* Init_SeqList() {/*构造空顺序表*/SeqList* L = (SeqList*)malloc(sizeof(SeqList));L->len = 0;return L; // 注意这里是可以返回局部变量的，不能返回的是局部变量的引用，不要搞混了 }void CreateSeqList(SeqList* L) {int i = 0;printf("Input length of list: ");scanf("%d",&L->len);printf("Input elements of List:\n");for (i = 1; i <= L->len; i++) // 注意data数组的下标是从0开始的scanf("%d",&L->data[i]); }void Insert_SeqList(SeqList* L, int i, datatype x) {if (L->len == MAXSIZE - 1){printf("SeqList is full\n");}else {if (i > L->len - 1 || i < 1)printf("The position is invalid");else {L->len++;int iTmp = L->len;while (iTmp > i){L->data[iTmp] = L->data[iTmp-1];iTmp--;}L->data[i] = x;}} }void print_SeqList(SeqList* L) {for (int i = 1; i <= L->len; i++)printf("%d ",L->data[i]);printf("\n"); }void Delete_SeqList(SeqList* L, int i) {if (i > L->len || i < 1)printf("The position is invalid\n");else {while (i <= L->len){L->data[i] = L->data[i + 1];i++;}L->len--;} }int Location_SeqList(SeqList* L, datatype x) {/*// 从前往后依次查找if (L->len == 0)printf("The SeqList is empty\n");else{int i = 1;while (i <= L->len){if (L->data[i] == x)return i;i++;}}*/L->data[0] = x;int i = L->len;while (L->data[i] != x)i--;return i;return 0; } - main.c
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include"SeqList.h"int main() {SeqList* L = Init_SeqList();CreateSeqList(L);print_SeqList(L);Delete_SeqList(L,2);puts("delete after: ");print_SeqList(L);Insert_SeqList(L,1,100);puts("insert after: ");print_SeqList(L);int x = 3; int i = Location_SeqList(L, x);printf("%d of position is %d\n",x,i);return 0; }
顺序表练习题
-
- 顺序表的逆置
// 线性表元素逆置 void Coverts(SeqList* A) {int left = 1, right = A->len;int iTmp = 0;while (left < right){iTmp = A->data[left];A->data[left] = A->data[right];A->data[right] = iTmp;left++;right--;} } -
- 有序顺序表的合并
SeqList* Merge(SeqList* A, SeqList* B, SeqList* C) {int iA = 1, iB = 1, iC = 1;C->len = A->len + B->len;while (iA <= A->len && iB <= B->len){if (A->data[iA] > B->data[iB])C->data[iC++] = B->data[iB++];elseC->data[iC++] = A->data[iA++];}while (iA <= A->len)C->data[iC++] = A->data[iA++];while (iB <= B->len)C->data[iC++] = B->data[iB++]; }
- 有序顺序表的合并
单链表
- LNode.h
#ifndef __LNODE_H__ #define __LNODE_H__ typedef char datatypeLNode; typedef struct node {datatypeLNode data;struct node* next; }LNode; LNode* CreateLinkList(); void PrintLinkList(LNode* head); int Length_LinkList(LNode* head); LNode* Get_LinkList(LNode* head, int i); void Insert_LinkList(LNode* head, int i, datatypeLNode x); void Del_LinkList(LNode* head, int i); #endif - LNode.cpp
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include"LNode.h"LNode* CreateLinkList() { LNode* head, * p,*tail;head = (LNode*)malloc(sizeof(LNode));head->next = NULL;tail = head;printf("Input any char string:\n");char ch;scanf("%c",&ch);while (ch!='#'){// 头插法/* p = (LNode*)malloc(sizeof(LNode));p->data = ch;p->next = head->next;head->next = p;scanf("%c", &ch);*/// 尾部插法p = (LNode*)malloc(sizeof(LNode));p->data = ch;p->next = NULL;tail->next = p;tail = tail->next;scanf("%c", &ch); }return head; } void PrintLinkList(LNode* head) {LNode* p = head->next;while (p){printf("%c ",p->data);p = p->next;}printf("\n");}int Length_LinkList(LNode* head) {LNode* p = head->next;int size = 0;while (p){size++;p = p->next;}return size; }LNode* Get_LinkList(LNode* head, int i) {if (i<0 || i>Length_LinkList(head)){ fprintf(stdout, "The input is invalid");exit(1);}LNode* p = head->next;while (i > 1){p = p->next;i--;}return p; }void Insert_LinkList(LNode* head, int i, datatypeLNode x) {LNode* p = (LNode*)malloc(sizeof(LNode));p->data = x;LNode* pre = Get_LinkList(head, i - 1);p->next = pre->next;pre->next = p; }void Del_LinkList(LNode* head, int i) {LNode* pre = Get_LinkList(head,i-1);LNode* del = pre->next;pre->next = del->next; }
循环链表
双向链表
- DLNode.h
#ifndef __DLNODE_H__ #define __DLNODE_H__ typedef char dlnodeDatatype;typedef struct dlnode {dlnodeDatatype data;struct dlnode* prior, * next; }DLNode;DLNode* CreateDLinkList(); void PrintDLinkList(DLNode* head); #endif // !__DLNODE_H__ - DLNode.c
#define _CRT_SECURE_NO_WARNINGS #include"DLNode.h" #include<stdio.h> #include<string.h> #include<stdlib.h>DLNode* CreateDLinkList() {DLNode* head = (DLNode*)malloc(sizeof(DLNode));head->next = head;head->prior = head;char ch = ' '; // 注意ch不去空字符即''scanf("%c",&ch);while (ch != '#'){DLNode* p = (DLNode*)malloc(sizeof(DLNode));p->data = ch;p->next = head->next;p->prior = head;head->next->prior = p;head->next = p;scanf("%c", &ch);}return head; }void PrintDLinkList(DLNode* head) {DLNode* p = head->next;while (p != head){printf("%c ", p->data);p = p->next;}puts("\n"); }
静态链表
- 用一维数组实现链表
应用举例
单链表逆置
- 使用头插法
void Convert(LNode* head) {LNode* p = head->next;head->next = NULL;// 使用尾插法while (p){LNode* tmp = p;p = p->next;tmp->next = head->next;head->next = tmp;}}
有序链表的合并
void LinkedMerge(LNode* A, LNode* B, LNode** C)
{// 将两个递增有序的链表合并到C中，是C中的元素递减有序// 思路:按序找到最小的元素，然后使用头插法LNode* pA = A->next, * pB = B->next;*C = A; // 注意无论任何类型指针，定义是必须先初始化为NULL，使用之前应该确定是否分配内存free(B);(*C)->next = NULL;//148#//2579#while (pA && pB){if (pA->data > pB->data){LNode* tmp = pB;pB = pB->next;tmp->next = (*C)->next;(*C)->next = tmp;}else {LNode* tmp = pA;pA = pA->next;tmp->next = (*C)->next;(*C)->next = tmp;}}printf("___________________________\n");while (pA){LNode* tmp = pA;pA = pA->next;tmp->next = (*C)->next;(*C)->next = tmp;}while (pB){LNode* tmp = pB;pB = pB->next;tmp->next = (*C)->next;(*C)->next = tmp;}
}约瑟夫环问题
- 使用带头结点的循环链表
// n个人，数到m的人出列，从第k个人开始 void Josephus(int n, int m, int k) {// 123456789# 2LNode* Jos = CreateCyclLinkList();PrintCyclLinkList(Jos);LNode* slow = Jos; // k默认从0开始LNode* fast = slow->next;printf("\nm= %d \n", m);int count = 1;printf("Josephus is : ");while (Length_CyclLinkList(Jos)!=0){ //printf("Josephus is : ");if (count == m){printf(" %c ", fast->data);count = 1;slow->next = fast->next;free(fast);fast = slow->next;if (fast == slow)break;}slow = fast;fast = fast->next;if (fast == Jos){slow = Jos;fast = slow->next;}count++;}printf("\n"); }
单链表只保存要求节点，其余节点删除
void Solution9(LNode* head, datatypeLNode x)
{LNode* front = head;LNode* rear = front->next;while (rear){if (rear->data != x){front->next = rear->next;free(rear);rear = front->next;continue;}front = rear;rear = rear->next;}}
单循环链表转化为双向循环链表
void Solution10()
{// 产生单向循环链表CyclLNode* head, * p, * tail;head = (CyclLNode*)malloc(sizeof(CyclLNode));head->next = NULL;tail = head;printf("Input any char string:\n");char ch;scanf("%c", &ch);while (ch != '#'){p = (CyclLNode*)malloc(sizeof(CyclLNode));p->data = ch;p->next = NULL;tail->next = p;tail = tail->next;scanf("%c", &ch);}tail->next = head;// 单向循环链表变双向循环链表CyclLNode* front = head;CyclLNode* rear = front->next;while (rear != head){rear->pre = front;front = rear;rear = rear->next;}rear->pre = front;// 倒着输出内容rear = head->pre;puts("\n");while (rear != head){printf(" %c ",rear->data);rear = rear->pre;}puts("\n");
}
递增输出单链表中的内容
void Solution11()
{LNode* head = CreateLinkList();PrintLinkList(head);printf("The length of list is %d\n",Length_LinkList(head));while (Length_LinkList(head) != 0){LNode* pre = head;LNode* next = pre->next;LNode* maxPre = NULL, * maxNext = NULL;int max = 1;while (next != NULL){if (next->data > max){max = next->data;maxPre = pre;maxNext = next;}pre = next;next = next->next;}printf(" %c ",max);maxPre->next = maxNext->next;free(maxNext);}
}
双向循环链表逆置(NB)
本质上也就是两个pre和next指针交换的问题
