数据结构（C++）第三周笔记
3.11 第三周
/* 预备知识：
1.指针：地址
2.指针变量：存放地址的变量
3.指针变量的定义：基类型 *指针变量名;
4.指针变量初始化：
1)在定义的同时赋初值
2)先定义，然后通过赋值语句赋值
5.指针的指向运算*
比如:int a=10,*p=&a;
cout<<p<<"\t"<<*p<<endl;
6.指针与一组数组
一组数组名称，代表其首元素的地址
如：int a[4]; 则a<=> &a[0]
7.
指针变量的加、减、自增、自减运算:通常是将指针变量和数组
关联起来。
将一个指针变量+常量，表示将数组的后面常量个元素
比如：int a[4],*p=a;表示p指向a[0]
p=p+2表示将p指向a[2]
p++、p--分别表示什么？
&a[3]-&a[1]?
8.结构体
1)结构体类型定义格式：
struct 结构体类型名称{
成员列表;
};
2)结构体变量定义：
结构体类型 结构体变量名列表;
3)结构体变量初始化
成员运算符 结构体变量名.结构体成员
4)给结构体变量输入值
9.new运算符
指针变量=new 类型;
//动态开辟类型所需要的字节长度的存储空间
//并且将该空间的首地址赋值给左边的指针变量
int *p;
p=new int;
10.delete语句
格式: delete 指针变量;
或 delete []指针变量;
11.构造函数
1）和类名同名，没有返回值，函数名左边不能加void
2)构造函数可以重载，可以由形参。
3)对象创建时由c++系统自动调用，其功能通常是给对象的数据成员进行初始化。
4）类定义，如果程序员没有定义构造函数，c++在编译时，自动产生一个空语句的构造函数。
12.析构函数
1）和类名同名，前面有~号，没有返回值，函数名左边不能加void
2）不能有参数，不能重载
3）对象消失是，c++自动执行，功能是通常用于做善后工作，比如，释放new动态开辟的空间
4）类定义，如果程序员没有定义析构函数，c++在编译时，自动产生一个空语句的析构函数
#include<iostream.h>
void main(){
int *p2;
p2=new int[4];
*p2=10;
*(p2+1)=20;
*(p2+2)=30;
*(p2+3)=40;
cout<<p2[0]<<" "<<p2[1]<<" "<<*(p2+2)<<" "
<<*(p2+3)<<endl;
delete []p2;
int *p;
p=new int;
*p=15;
cout<<p<<" "<<*p<<endl;
delete p;
}
*/
/*单链表
1.定义存放数据元素和逻辑关系的结构体类型
2.定义单链表(带头结点的单链表)类
*/
#include<iostream>
using namespace std;
template<typename T>
struct Node{
T data;
Node<T> *next;
};
template<typename T>
class linkListHead{
Node<T> *first;
public:
linkListHead(){//无参构造函数，创建空的单链表
first=new Node<T>;
(*first).next=NULL;//(*first).next<=>first->next
}
linkListHead(T a[],int n);//有参构造函数，创建单链表，
//用尾插法a数组的n个元素存储在链表的各结点的data成员中
void Insert(int i,T x);//插入函数
T Delete(int i);//删除函数
int Length();//求表长函数
T Get(int i);//按位取值函数
int Locate(T x);//按值查找函数
bool Empty(){//判空函数
if(!(first->next)) return true;
else return false;
}
~linkListHead();//析构函数
};
template<typename T>
linkListHead<T>::linkListHead(T a[],int n){
Node<T> *rear,*s;//定义指针变量
//创建头结点，将其地址赋值给first和rear
rear=first=new Node<T>;
for(int i=0;i<n;i++){
s=new Node<T>; //产生结点，赋值给s变量
s->data=a[i];//将a[i]赋值给s->data
rear->next=s;//将rear->next指向s
rear=s;//将s作为新的尾结点
}
rear->next=NULL;//将尾结点的next成员置空
}
template<typename T>
void linkListHead<T>::Insert(int i,T x){
if(i<1) throw"位置不当\n";
//找第i-1个结点
Node<T> *s,*p=first;
int count=0;
while(p!=NULL&&count<i-1){
p=p->next;//p后移
count++;//计数器变量加1
}
if(p==NULL) throw"位置不当\n";
s=new Node<T>;
s->data=x;
s->next=p->next;
p->next=s;
}
template<typename T>
T linkListHead<T>::delete(int i){//删除函数
if (i<1)throw"位置不当\n";
int coumt=0;
Node<T> *p=first;
while(p!=NULL&&count<i-1){
count++;
p=p->next;
}
if(p==NULL||p!=NULL&&p->next==NULL)throw"位置不当\n";
q=p->next;
T x=q->data;
p->next=q->next;
delete q;
return x;
}
template<typename T>
int linkListHead<T>::Length(){//求表长b
int count=0;
Node<T> *p=first->next;
while(p!=NULL){
count++;
p=p->next;
}
return count;
}
template<typename T>
T linkListHead<T>::Get(int i){
if(i<1)throw"位置不当\n";
int count=1;
Node<T> *p=first->next;
while(p!=NULL&&count<i){
count++;
p=p->next;
}
if(p==NULL)throw"位置不当\n";
return p->data;
}
template<typename T>
int linkListHead<T>::Locate(T x){
int count=1;
Node<T> *p=first->next;
while(p!=NULL&&p->data!=p->next)}
count++;
p=p->next;
}
if(p!=NULL) return count;
else return 0;
}
template<typename T>
linkListHead<T>::~linkListHead(){//析构函数
//对象消失是，c++自动执行
//通常用于做善后工作，比如释放now动态开辟的空间
Node<T> *p=first;
while(p!=NULL){
first=first->next;
delete P;
p=first;
}
}
int main(void){
int a[4]={20,50,10,60};
linkListHead<int> list(a,4);
linkListHead<char> list2;
cout<<list2.Empty()<<endl;
cout<<list1.Empty()<<endl;
cout<<list1.Length()<<endl;
try{cout<<list.Get(5)<<endl;}
catch (char *wr){cout<<wr;}
cout<<list1.Locate(80)<<endl;
try{ list1.Insert(3,70);list1.Insert(8,100);}
catch(char *wr){cout<<wr;}
try{cout<<list1.Delete(2)<<endl;
catch(char *wr}{cout<<wr;}
cout<<list1.Length()<<endl;
try{cout<<list1.Get(2)<<endl;
catch(char *wr){cout<<wr;}
