|
目录
1.单链表的定义。
2.定义一个为L的单链表。
3.交换第k个节点，和第k+1个节点的值。
4.如果有LNode *p,*s,若p指向其中一个节点（该节点不为空），s指向一个新的节点，要求：
(1).在p后面插入节点s。
(2).在p节点前插入s。
第一种方法：
第二种方法：
?5.求单链表的长度
6.按下标取单链表中的某个元素。
7.按值查找操作。
8.插入元素
9.删除操作
10.建立单链表
(1).头插法
(2).尾插法
?
1.单链表的定义。
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
2.定义一个为L的单链表。
LNode *L;//或者LinkList L;
3.交换第k个节点，和第k+1个节点的值。
bool change(LinkList L,int k)
{
LNode *p=L;//让p指向头节点
int j=0; //计数器，帮助找到第k个节点
while(p->next!=NULL&&j<k)//遍历链表，直到找到第k个节点
{
p=p->next;
j++;
}
if(!(p->next)&&j>k) //需要保证p的后继节点存在
return false;
//交换k和k+1节点的值
int x=p->data;
p->data=p->next->data;
p->next->data=x;
return true;
}
4.如果有LNode *p,*s,若p指向其中一个节点（该节点不为空），s指向一个新的节点，要求：
(1).在p后面插入节点s。
s->next=p->next;
p->next=s;
(2).在p节点前插入s。
第一种方法：
遍历找到p前面的节点。
void insert()
{
LNode *q=L;
while(q->next!=p) q=q->next;
s->next=q->next;//或者s->next=p;
q->next=s;
}
时间复杂度为O(n),空间复杂度为O(1)。
第二种方法：
假设原来的序列是x，y，p指向y，需要在y前面插入一个节点s，此时顺序为x，s，y，如y后面插入节点s?，那么此时的顺序为x，y，s，我们发现只要交换y和s节点的数据域即可。
void insert()
{
//在p后面插入节点
s->next=p->next;
p->next=s;
//交换节点p和s的数据域,此时s就是p后面的一个节点
int x=p->data;
p->data=p->next->data;
p->next->data=x;
}
时间复杂度为O(1),空间复杂度为O(1)。
?5.求单链表的长度
遍历链表即可。
int Listlength(LinkList L)
{
int j=0;
LNode *p=L;
while(p->next!=NULL)
{
j++;
p=p->next;
}
return j;
}
6.按下标取单链表中的某个元素。
遍历找到下标。
bool GetElem(LinkList L,int i,int &e)//因为需要把值传回去，加&
{
LNode *p=L;
int j=0;
while(p&&j<i)
{
p=p->next;
j++;
}
if(!p||j>i) return false;
e=p->data;
return true;
}
//时间复杂度O(n)
7.按值查找操作。
该操作需要依次用单链表中的元素与所给数据进行比较。
具体方法：设置一个指针p依次指示每个节点，比较e和p所指节点的值，如果p->data==e,表示查找成功，返回该元素的地址；否则继续进行搜索，直到表尾；如果没有找到，表示查找失败，返回NULL
LNode &LocateElem(LinkList L,int e)
{
LNode *p;
p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
if(!p) return NULL:
return p->next;
}
8.插入元素
//基本操作
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
完整代码：
bool ListInsert(LinkList &L,int i,int e)//在i之前插入一个节点
{
LNode *p=L;
int j=0;
while(p&&j<i-1)//找到i-1节点
{
p=p->next;
++j;
}
if(!p||j>i-1) //参数不合法，i小于1或者大于表长+1
return false;
s=new LNode; //创建新节点
if(!s) exit(-2);//创建失败
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
9.删除操作
假设删除第i个节点后面的节点，假设p指向第i个节点，那么之间p->next=p->next->next;
bool ListDete(LinkList &L,int i,int &e)
{
LNode *p=L;
int j=0;
while(p->next&&j<i-1)//寻找i-1个节点，并令p指向该结点
{
p=p-next;
++j;
}
if(!(p->next)||j>i-1) return false;
LNode q=p->next;
p->next=q->next;
e=q->data;
delete q; //释放空间
return true;
}
10.建立单链表
(1).头插法
顺序相反，如果插入顺序是x,y,z,在单链表中是z，y，x。
void GreateList(LinkList &L,int n)
{
L=(LNode *)malloc(sizeof(LNode));
L->next=NULL;
for(int i=0;i<n;i++)
{
p=new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
(2).尾插法
顺序相同。
void GreateList(LinkList &L,int n)
{
L=new LNode;
LNode r=L;
for(int i=0;i<n;i++)
{
p=new LNode;
cin>>p->data;
r->next=p;
r=p;
}
r->next=NULL;//将尾结点置空
}
|