7.21 复习数据结构相干知识【主链表】
顺序表 链表 栈 队列之间的关系[*]顺序表：array list---->基于数组实现的线性表，元素在内存中是一连存储的。
[*]链表：linked list ---->通过指针将一系列节点连接起来的线性表
[*]单链表：next指针
[*]双链表：prior+next指针 //430扁平化多级双向链表
[*]栈：stack---->线性数据结构，先进后出，实现方式：链表/顺序表 pop push top
[*]队列：queue---->线性数据结构，先进先出，实现方式：顺序表/链表 enqueue dequeue
顺序表 和 链表 都是线性表，前者基于数组实现，后者基于指针实现。
栈 和 队列 是两种特殊的线性表，它们可以基于顺序表或链表实现，但在操纵原则上有所不同，栈是LIFO，队列是FIFO。
//单链表
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode;
//双链表
typedef struct DLNode{
ElemType data;
struct DLNode* next;
struct DLNode* prior;
}DLNode;
//顺序表
typedef struct Sqlist{
ElemType data;
int length;
}Sqlist;
训练题(手写代码内容)
【说明】由于考试中通常更注意基本概念和传统方法，理解链表的基本操纵会帮助掌握这些概念。发起掌握不使用哑节点的方法，以便在考试中灵活应对各种题目。
[*]A和B是两个带头节点的元素递增有序的单链表。设计一个算法将A 和B 合并成非递减有序的单链表C。【21 合并两个有序链表】
void Merge(LNode *& A,LNode *&B,LNode *&C){
//排除AorB为空链表的情况，不令C=A orB来获取相同的头节点。
C = (LNode*)malloc(sizeof(LNode));
C->next = NULL;
LNode *p = A->next;
LNode *q = B->next;
LNode *r;
r = C;
while(p&&q){
if(p->data <= q->data){
r->next = p;
p = p->next;
}else{
r->next = q;
q = q->next;
}
r = r->next;
}
if(p){r->next = p;}
else{r->next = q;}//如果二者同时结束，r->next = NULL;就刚好
}
[*]尾插法建立单链表
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode;
void Createl(LNode *&L,ElemType a[],int n){
L = (LNode*)malloc(sizeof(LNode));
//增加内存分配失败检查
if(L == NULL){
printf("Memory allocation failed\n");
return;
}
L->next = NULL;
LNode *r = L;//尾指针初始化为头节点
for(int i = 0 ; i < n ; i++){
LNode *s = (LNode*)malloc(sizeof(LNode));
if(s == NULL){
printf("Memory allocation failed\n");
return;
}
s->data = a;
s->next = NULL;
r->next = s;//将新节点连接到链表的尾部
r = s;//更新尾指针为新节点
}
}
[*]头插法建立单链表
void CreateH(LNode *&L, Elemtype a[],int n){
L = (LNode*)malloc(sizeof(LNode));
if(L == NULL){
printf("Memory allocation failed.\n");
return;
}
L->next = NULL;
for(int i = 0; i < n ; i++){
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s == NULL){
printf("Memory allocation failed.\n");
return;
}
s->data = a;
s->next = L->next;
L->next = s;
}
}
头插法不需要新建LNode* r;令r = L;r一般做尾指针，在尾插法中才会需要。
[*]查找带头节点的单链表L中是否存在节点x，假如存在则删除x节点。【237 删除链表中的节点】条件：只存在一个这样的节点
int SearchDel(LNode *&L, ElemType x) {
LNode *prev = L, *curr = L->next;
while (curr) {
if (curr->data == x) {
prev->next = curr->next;
free(curr);
return 1;
} else {
prev = curr;
curr = curr->next;
}
}
return 0;
}
[*]使用尾插法建立双链表
void CreateDL(DLNode *&L, ElemType a[], int n) {
L = (DLNode*)malloc(sizeof(DLNode));
if (L == NULL) {
printf("Memory allocation failed.\n");
return;
}
L->prior = NULL;
L->next = NULL;
DLNode* r = L; // 尾指针
for (int i = 0; i < n; i++) {
DLNode* s = (DLNode*)malloc(sizeof(DLNode));
if (s == NULL) {
printf("Memory allocation failed.\n");
return;
}
s->data = a;
s->prior = r;
s->next = NULL;
r->next = s;
r = s;
}
}
[*]双链表查找值x
DLNode *Search(DLNode *L, ElemType x){
DLNode *s = L->next;
while(s){
if(s->data == x){
return s;
}
s = s->next;
}
return NULL;
}
[*]双链表在节点p后插入s
void InsertAfter(DLNode *p, DLNode *s) {
s->next = p->next;
s->prior = p;
if (p->next != NULL) {// 如果p的next不为空，将p的next的prior指向s
p->next->prior = s;
}
p->next = s; // 将p的next指向s
}
[*]双链表删除p的next节点
void DeleteNext(DLNode *p) {
DLNode *q = p->next;
if (q != NULL) { // 如果q不为空，继续删除操作
p->next = q->next;
if (q->next != NULL) { // 如果q的next不为空，将q的next的prior指向p
q->next->prior = p;
}
free(q); // 释放q节点
}
}
7 8 两个表明部门轻易忘记
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]