赞
踩
一,双链表
单链表只包含后继节点的指针,从一个节点出发只能找到后继的各个节点
双链表又添加一个指针域,指向前驱节点,表头节点的prior指向null,表尾节点的next指向null。
(1)双链表的初始化
(2)双链表的插入
(3)双链表的删除
(4)双链表的遍历
二,循环链表
(1)循环单链表,从一个节点出发可以找到其他任何一个节点
(2)循环双链表,表头节点的prior指向表尾节点,表尾节点的next指向头结点。
三,单链表的基本操作代码示意:1-12
- #include <stdlib.h>
- #include <stdio.h>
- typedef struct LNode{
- int data;//每个节点存放一个int类型的数据元素
- Struct Lnode *next;//指针指向下一个节点
- }LNode,*LinkList;//将struct LNode重命名为LNode,并表示使用LinkList作为一个指针指向Struct lNODE.
- //1,初始化不带头节点 ,LNode *L等价与LinkList L,声明一个指向单链表的第一个节点的指针
- bool InitList1(LinkList &L){
- L=NULL;
- return true;
- }
- //2,初始化带头节点
- bool InitList2(LinkList &L){
- L=(LNode *)malloc(sizeof(LNode));
- L->next=NULL;
- return true;
- }
- //3, 带头节点的插入
- bool InsertList1(LinkList &L,int i,int e){
- if(i<1){
- return false;
- }
- LNode *p;//定义一个指针p指向当前扫描到的节点
- int j=0;//记录p指向第几个节点
- p=L;//从头节点开始 ,l指向头结点
- while(p!=NULL&&j<i-1){
- p=p->next;
- j++;
- }
- LNode *s=(LNode*)malloc(sizeof(LNode));
- s->data=e;
- s->next=p->next;
- p->next=s;
- return true;
- }
- //4,不带头结点的插入,需考虑第一个特殊节点
- bool InsertList1(LinkList &L,int i,int e){
- if(i<1){
- return false;
- }
- //插入第一个节点时候不同
- if(i==1){
- LNode *s=(LNode*)malloc(sizeof(LNode));
- s->data=e;
- s->next=L;//新节点指向l指向的节点也就是头结点
- L=s;//l指向新节点
- return true;
- }
- LNode *p;//定义一个指针p指向当前扫描到的节点
- int j=0;//记录p指向第几个节点
- p=L;//从头节点开始 ,l指向头结点
- while(p!=NULL&&j<i-1){
- p=p->next;
- j++;
- }
- LNode *s=(LNode*)malloc(sizeof(LNode));
- s->data=e;
- s->next=p->next;
- p->next=s;
- return true;
- }
- //5,不带头节点的插入之:前插,偷天换日,实际是与p节点交换了数据
- bool InsertList2(LinkList p,int e){
- if(p==NULL){
- return false;
- }
- LNode *s=(LNode *)malloc(sizeof(LNode));
- if(s==NULL){
- return false;
- }
- s->next=p->next;
- p->next=s;
- s->data=p->data;
- p->data=e;
- return true;
- }
- //6,不带头节点的插入之:后插
- bool InsertList2(LinkList &p,int e){
- if(p==NULL){
- return false;
- }
- LNode *s=(LNode*)malloc(sizeof(LNode));
- if(s==NULL){
- return false;
- }
- s->data=e;
- s->next=p->next;
- p->next=s;
- return true;
- }
- //7,带头节点的删除,循换找到位序-1的节点,定义q指向要被删除的节点,断开该节点,最后释放q节点存储空间
- bool DeleteList(LinkList &L,int i,int &e){//e为引用类型,要带回数据
- if(i<1){
- return false;
- }
- LNode *p; //定义一个指针指向当前扫描到的节点
- int j=0;//记录p指向第几个节点
- while(p!=NULL && j<i-1){
- p=p->next;
- j++;
- }
- if(p==NULL){
- return false;
- }
- if(p->next==NULL){
- return false;
- }
- LNode *q=p->next;//q指向被删除节点
- e=q->data;//e返回删除元素
- p->next=q->next;//断开
- free(q);
- return true;
- }
- //8,带头节点的指定节点删除
- bool DeleteList(LinkList &p){
- if(p==null){
- return false;
- }
- LNode *q=p->next;
- p->data=p->next->data;
- p->next=q->next;
- free(q);
- return true;
- }
- //9,带头节点按位查找
- LNode *LocateElem(LinkList &L,int i){
- if(i<1){
- return NULL;
- }
- LNode *p;//指针p指向当前扫描的节点
- p=L;//从头结点开始
- int j=0;
- while(p!=NULL&&j<i){
- p=p->next;
- j++;
- }
- return p;
-
- }
- //10,带头节点的按值查找
- LNode *Getelem(LinkList &L,int e){
- LNode *p=L;
- while(p!=NULL&&p->data!=e){
- p=p->next;
- }
- return p;
- }
- //11,求表的长度
- int Length(LinkList &L){
- LNode *p=L;
- int j=0;
- while(p->next!=NULL){
- p=p->next;
- j++;
- }
- return j;
- }
- //12,建立单链表,尾插法
- LinkList List_Tailnsert(LinkList &L){
- L=(LinkList)malloc(sizaof(LNode));
- LNode *s,*r=L;
- int x;
- scanf("%d",&x);
- while(x!=9999){
- s=(LNode *)malloc(sizeof(LNode));
- s->data=x;
- r->next=s;
- r=s;
- }
- r->next=NULL;//r为尾指针,此时为空
- return L;
- }
- //12,头插法
- LinkList List_Headnsert(LinkList &L){
- L=(LinkList)malloc(sizaof(LNode));
- L->next=NULL;
- LNode *s;
- int x;
- scanf("%d",&x);
- while(x!=9999){
- s=(LNode *)malloc(sizeof(LNode));
- s->data=x;
- s->next=L->next;
- L->next=s;
- scanf("%d",&x);
- }
- return L;
-
- }
四,每日一题:剑指 Offer 24. 反转链表
(1)双指针
- class Solution {
- public ListNode reverseList(ListNode head) {
- ListNode cur=head,per=null;//定义cur指向头节点,per指向null
- while(cur!=null){
- ListNode temp=cur.next;//定义temp
- cur.next=per;//修改指向
- per=cur;//per
- cur=temp;
- }
- return per;
- }
- }
五,理论知识:
(1)java向上转型,比如char自动转为int类型
(2)数组引用类型的变量的默认值为 null
(3)执行顺序优先级:静态域,main(),构造代码块,构造方法。
静态块:用static申明,JVM加载类时执行,仅执行一次
构造块:类中直接用{}定义,每一次创建对象时执行
(4)线程安全问题:Vector相当于一个线程安全的List
HashMap是非线程安全的,其对应的线程安全类是HashTable
Arraylist是非线程安全的,其对应的线程安全类是Vector
StringBuffer是线程安全的,相当于一个线程安全的StringBuilder
Properties实现了Map接口,是线程安全的
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。