本帖最后由 小熊孩 于 2020-9-24 21:55 编辑
待标题有朝一日变为成神之路,hhhh~嗝~~
当回首往事的时候，不因虚度年华而悔恨.
本帖为数据结构笔记,持续更新,不再开新帖.
时间 : 2020年9月23日
单链表的算法
1.单链表的算法
[C++] 纯文本查看 复制代码 //定义节点
typedef struct LNdode
{
ElemType data; //数据域
struct LNode *next; //指向下一个节点的指针
}LinkList;
1) 才用头插法建立单链表
[C++] 纯文本查看 复制代码 void CreateListF(LinkList *&L, ElemType a[], int n){
LinkList *s; int i;
L = (LinkList *)malloc(sizeof(LinkList));
L->next = null;
for(i=0; i<n; i++)
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
s->next = L->next;
L->next = s;
}
}//时间复杂对为O(n) 2) 采用尾插法建立单链表 [C++] 纯文本查看 复制代码 void CreateListF(LinkList *&L, ElemType a[], int n)
{
LinkList *s, *r; int i;
L = (LinkList *)malloc(sizeof(LinkList));
r = L;
for(i=0; i<n; i++)
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
r->next= s;
r = s;
}
r->next = null;
}//时间复杂对为O(n)2.单链表的基本运算算法 1) 暗元素查找算法 [C++] 纯文本查看 复制代码 int LocateElem(LinkList *L, ElemType e)
{
LinkList *p = L->next;
int n = 1;
while(p!=null && p->data !=e)
{
p = p->next;
n++;
}
if(p==null)
return 0;
else
return n;
} 2)插入节点操作 [C++] 纯文本查看 复制代码 s->next = p->next;
p->next = s; 3) 删除节点操作 [C++] 纯文本查看 复制代码 p->next = p->next->next; 3.有序但你链表的归并算法 1) 方法一 [C++] 纯文本查看 复制代码 void Merge(LinkList *L1, LinkList *L2, LinkList *&L3)
{
LinkList *p = L1->next, *q = L2->next, *r, *s;
L3 = (LinkList *)malloc(sizeof(LinkList));
while(p!=null && q!null)
{
if(p->data < q->data)
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = p->data;
p = p->next;
r->next = s;
r = s;
}
else
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = q->data;
q = q->next;
r->next = s;
r = s;
}
}
if(q != null)
p = q;
while(p != null)
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = p->data;
p = p->next;
r->next = s;
r = s;
}
r->next = null;
}//时间复杂度/空间复杂度 O(m+n) 2) 方法二 [C++] 纯文本查看 复制代码 /*自我感觉这个地方我写的可能不对,希望大佬们帮我审阅并指正一下,谢谢哦.*/
void Merge(LinkList *L1, LinkList *L2, LinkList *&L3)
{
LinkList *p = L1->next, *q = L2->next, *r;
L3 = L1;
free(L2);
r = L3;
while(p!=null && q!null)
{
if(p->data < q->data)
{
r->next = p;
p = p->next;
}
else
{
r->next = q->next;
q = q->next;
}
r = r->next;
}
if(q != null)
p =q;
r->next = null;
}//时间复杂度O(m+n) 空间复杂度O(1)
时间:2020年9月24日 双链表的算法 1.双链表节点定义 [C] 纯文本查看 复制代码 //定义节点
typedef struct LNdode
{
ElemType data; //数据域
struct DLNode *prior; //指向前驱节点
struct DLNode *next; //指向下一个节点的指针
}DLinkList; 1)采用头插法建立双链表 [C] 纯文本查看 复制代码 void CreateDListF(LinkList *&L, ElemType a[], int n)
{
DLinkList *s; int i;
L = (DLinkList *)malloc(sizeof(DLinkList));
L->next = L->prior = null;
for(i=0; i<n; i++)
{
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = a[i];
s->next = L->next;
if(L->next != null)
{
L->next->prior = s;
}
L->next = s;
s->prior = L;
}
}//时间复杂对为O(n) 2)采用尾插法建立双链表 [C] 纯文本查看 复制代码 void CreateDListR(LinkList *&L, ElemType a[], int n)
{
DLinkList *s, *r; int i;
L = (DLinkList *)malloc(sizeof(DLinkList));
r = L;
for(i=0; i<n; i++)
{
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = a[i];
r->next = s;
s->prior = r;
r = s;
}
}//时间复杂对为O(n)2.双链表的基本运算算法 1)查找元素值的节点 [C] 纯文本查看 复制代码 int Finfnode(DLinkList *L, ElemType e)
{
DLinkList *p = L->next;
int n = 1;
while(p!=null && p->data !=e)
{
p = p->next;
n++;
}
if(p==null)
return 0;
else
return n;
}//时间复杂对为O(n) 2)插入节点 [C] 纯文本查看 复制代码 /**[align=left]* 核心代码[/align][align=left]* s->next = p->next;[/align][align=left]* p->next->prior = s;[/align][align=left]* s->prior = p;[/align][align=left]* p->next = s;[/align][align=left]*/[/align]int ListInsert(DLinkList *&L, int i, ElemType e)
{
int j = 0;
DLinkList *p = L, *s;
while(j<i-1 && p!=null)
{
p = p->next;
j++;
}
if(p == null)
{
return 0;
}
else
{
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = e;
s->next = p->next;
if(p->next != null)
{
p->next->prior = s;
}
s->prior = p;
p->next = s;
return 1;
}
} 3)删除节点操作 [C] 纯文本查看 复制代码 /**
* 核心代码
* p->next = q->next;
* q->next->prior = p;
*/
int ListDelete(DLinkList *&L, int i, ElemType &e)
{
int j = 0;
DLinkList *p = L, *q;
while(j<i-1 && p!=null)
{
p = p->next;
j++;
}
if(p == null)
{
return 0;
}
else
{
q = p->next;
if(q==null)
{
renturn 0;
}
p->next = q->next;
if(p->next != null)
{
p-next->prior = p;
}
free(q);
return 1;
}
}
不知道以后这边会写啥,先圈起来留个地.
附件为MD格式的笔记,内容与帖子内容完全一致,跟随更新,根据需要下载.
附件为MD格式的笔记,内容与帖子内容完全一致,跟随更新,根据需要下载.
附件为MD格式的笔记,内容与帖子内容完全一致,跟随更新,根据需要下载.
数据结构笔记.rar
(5.31 KB, 下载次数: 15)
|
发表于 2020-9-23 23:50
