数据结构学习

2024-07-12 00:23| 来源: 网络整理| 查看: 265

线性表的结构体定义 #define maxSize 100 //定义一个整型常量maxSize,值为100 1.顺序表的结构体定义 typedef struct { int data[maxSize]; int length; }Sqlist;

也可以这么定义,简洁:

int A[maxSize]; int n; 2.单链表结点定义 typedef struct LNode { int data; //存放结点数据域 struct LNode *next; //指向后继结点的指针 }LNode; //定义单链表结点类型 3.双链表结点定义 typedef struct DLNode { int data; //存放结点数据域 struct DLNode *prior; //指向前驱结点的指针 struct DLNode *next; //指向后继结点的指针 }DLNode; 4.为结点分配和释放内存 LNode *A = (LNode *)malloc(sizeof(LNode)); free(A); 顺序表的操作 1.按元素值的查找算法

在顺序表中查找第一个值等于e的元素，并返回其下标，代码如下:

int findElem(Sqlist L,int e) { int i; for(i = 0;i int i; if(pL.length||L.length == maxSize) return 0; for(i=L.length-1;i>=p;--i) L.data[i+1]=L.data[i]; //从后往前，逐个将元素往后移动一个位置 L.data[p]=e; ++(L.length); //表内元素多了一个，因此表长自增1 return 1; //插入成功，返回1 } 3.删除顺序表L中下标为p的元素，成功返回1，否则返回0，并将删除元素的值赋给e。 int deleteElem(Sqlist &L,int p,int &e) { int i; if(pL.length-1) return 0; //位置不对返回0，代表删除不成功 e = L.data[p]; //将被删除元素赋值给e for(i=p;i if(p->datadata) { r->next=p; p=p->next; //这顺序千万不能颠倒 r=r->next; } else { r->next=q; q=q->next; r=r->next; } } r->next=NULL; //这句话可以不加，因为下面两句比会执行其中一句 if(p!=NULL) r->next = p; //如果p有剩余，直接将r下一个结点指向p if(q!=NULL) r->next = q; //如果q有剩余，直接将r下一个集结点指向q } 尾插法建立单链表 void merge(LNode *&C,int a[],int n) { LNode *s,*r; //s用来指向新申请的结点，r始终指向C的终端节点 int i; C = (LNode *)malloc(sizeof(LNode)); //申请C的头结点空间 C->next = NULL; r = C; for(i=0;i LNode *s; int i; C=(LNode *)malloc(sizeof(LNode)); C->next = NULL; for(i=0;i LNode *p = A->next; LNode *q = B->next; LNode *s; C=A; C->next=NULL; free(B); while(p!=NULL&&q!=NULL) { if(p->datadata) { s = p; p = p->next; s->next = C->next; C->next = s; } else { s = q; p = q->next; s->next = C->next; C->next = s; } } //这区别于尾插法 while(p!=NULL) { s = p; p = p->next; s->next = C->next; C->next = s; } while(q!=NULL) { s = q; q = q->next; s->next = C->next; C->next = s; } } 头插法关键语句 s->next = C->next; C->next = s; 删除结点

假设p为指向a的指针，则只需将p的指针域next指向原来p的下一个结点的下一个结点即可，即:

p->next=p->next->next;

完整的删除操作是:

q=p->next; p->next = p->next->next; free(q); //调用函数free()来释放q所指结点的内存空间例题

查找链表C(带头结点)中是否存在一个值为x的结点，若存在，则删除该结点并返回1，否则返回0。

int findAndDelete(LNode *C,int x) { LNode *p,*q; p = C; while(p->next!=NULL) //循环找到要删除结点的前一个结点 { if(p->next->data == x) break; p = p->next; } if(p->next == NULL) return 0; else { q = p->next; p->next = q->next; free(q); return 1; } }

删除结点要找到要删除结点的前驱结点，而不是直接指向所要删除结点本身。

双链表的操作采用尾插法建立双链表 void createDlistR(DLNode *&L,int a[],int n) { DLNode *s,*r; int i; L=(DLNode *)malloc(sizeof(DLNode)); L->prior = NULL; //前指针 L->next = NULL; //后指针 r = L; //和单链表一样，r始终指向终端结点，开始头结点也是尾结点 for(i=0;i DLNode *p=C->next; while(p!=NULL) { if(p->data == x) break; p = p->next; } return p; } 插入结点的算法

假设在双链表中p所指的结点之后插入一个结点s，其操作语句如下:

s->next = p->next; s->prior = p; p->next = s; p->next->prior = s; //假如p指向最后一个结点，则本行去掉删除结点的算法

设要删除双链表中p结点的后继结点，其操作语句如下:

q = p->next; p->next = q->next; q->next->prior = p; free(q);

【本文地址】

公司简介

联系我们