데이터 구조 와 알고리즘 --- 자바 실현 (제2 장 데이터 구조 상)
15065 단어 데이터 구조 와 알고리즘
1. 데이터 구조의 개술
2. 데이터 구조의 기본 적 인 의미
3. 데이터 구조 에서 의 기본 개념
(Data): 데 이 터 는 정보의 매개체 이다.
같은 논리 구 조 는 서로 다른 저장 구 조 를 가 질 수 있다 (예 를 들 어 선형 표 는 순서 표 화해시키다 링크
같은 저장 구조 에 도 서로 다른 데이터 연산 집합 이 있 을 수 있다 (예 를 들 어 선형 표 의 삽입 과 삭제 위치 가 다르다. 창고.
5. 데이터 구조의 분류
시작 점 과 끝 점 이 하나 밖 에 없다.
최대 하나의 직접 전구 결점 과 하나의 직접 후계 결점 만 있다.
2. 비 선형 구조: 각 결점 간 은 다 대응 관계 이다.
비 선형 구조 비 공 집합
하나의 결점 은 여러 개의 직접 전구 결점 과 직접 후계 결점 이 있 을 수 있다
6. 데이터 구조의 몇 가지 저장 방식
장점: 데이터 와 조작 을 한데 묶 어 정보의 숨 김 을 실현 한다.
자바 에 서 는 인터페이스 로 ADT 를 나타 내 고 인터페이스의 실현 류 로 ADT 를 실현 하 며 ADT 는 개념 층 의 추상 이 고 인 터 페 이 스 는 실현 층 의 추상 이다.
8. 상용 데이터 구조
배열 (Array), 스 택 (Stack), 대기 열 (Queue), 링크 (Linked) List), 트 리 (Tree), 그림 (Graph), 더미 (Heap), 산 목록 (Hash)
9. 적합 한 데이터 구 조 를 선택 하여 실제 문 제 를 해결한다.
수치 계산 문제: 수학 과 공학 의 계산 알고리즘
비수 치 계산 문제: 데이터 구조
10. 선형 표
1. 선형 표 란 무엇 인가
n (n > 0) 개 데이터 요소 로 구 성 된 유한 서열.
2. 선형 표 의 기본 연산
초기 화, 계산 표 길이, 결점 가 져 오기, 결점 찾기, 결점 삽입, 결점 삭제
11. 순서 표 구조
1. 순서대로 저장 하 는 선형 표. 이 선형 표 의 결산 점 은 논리 적 순서에 따라 컴퓨터 의 연속 적 인 저장 장치 에 저장 된다.
2. 조작 순서 표 연산 의 기본 규칙: LOC(ai)= LOC(a1) + (i-1)* c (1<= i <= n)
3. 순서 표 구조의 프로 그래 밍
코드 표시:
import java.util.Scanner;
/**
*
*
*/
//
class DATA {
String key; //
String name;
int age;
} //
//
class SLType { //
static final int MAXLEN = 2; // （ ）
DATA[] ListData = new DATA[MAXLEN + 1]; //
int ListLen; //
//
void SLInit(SLType SL) { //
SL.ListLen = 0; //
}
// （ L ）
int SLLength(SLType SL) {
return SL.ListLen;
}
//
int SLInsert(SLType SL, int n, DATA data) {
int i;
if (SL.ListLen >= MAXLEN) {
System.out.println(" ， ");
return 0; //
}
if (n < 1 || n > SL.ListLen - 1) {
System.out.println(" ， ！");
return 0;
}
//
for (i = 0; i < SL.ListLen; i++) {
SL.ListData[i + 1] = SL.ListData[i];
}
SL.ListData[n] = data;
SL.ListLen++;
return 1; //
}
//
int SLAdd(SLType SL, DATA data) {
if (SL.ListLen >= MAXLEN) {
System.out.println(" ， ");
return 0;
}
SL.ListData[++SL.ListLen] = data;
return 1;
}
//
int SLDelete(SLType SL, int n) {
int i;
if (n < 1 || n > SL.ListLen + 1) {
System.out.println(" ， ！");
return 0;
}
for (i = 0; i < SL.ListLen; i++) {
SL.ListData[i] = SL.ListData[i + 1];
}
SL.ListLen--;
return 1;
}
/**
* ( )
*/
//
DATA SLFindByNum(SLType SL, int n) {
if (n < 1 || n > SL.ListLen) {
System.out.println(" , !");
return null;
}
return SL.ListData[n];
}
//
int SLFindByCont(SLType SL, String key) {
int i;
for (i = 1; i <= SL.ListLen; i++) {
if (SL.ListData[i].key.compareTo(key) == 0) {
return i; //
}
}
return 0;
}
//
int SLAll(SLType SL) {
int i;
for (i = 1; i <= SL.ListLen; i++) {
System.out.println(SL.ListData[i].key + " " + SL.ListData[i].name + " " + SL.ListData[i].age);
}
return 0;
}
}
//-------------------------------------------------------------------//
/**
*
*/
public class SortTable {
public static void main(String[] args) {
int i;
SLType SL = new SLType();
DATA pdata;
String key;
System.out.println(" !");
SL.SLInit(SL); //
System.out.println(" ");
Scanner scanner = new Scanner(System.in);
do { //
System.out.println(" ( )");
DATA data = new DATA();
data.key = scanner.next();
data.name = scanner.next();
data.age = scanner.nextInt();
if (data.age != 0) { // 0,
if (SL.SLAdd(SL, data) == 0) { //
break;
}
} else { // 0
break;
}
} while (true);
System.out.println(" :");
SL.SLAll(SL); //
System.out.println(" :");
i = scanner.nextInt();
pdata = SL.SLFindByNum(SL, i);
if (pdata != null) {
System.out.println(" " + i + " :" + pdata.key + " " + pdata.name + " " + pdata.age);
}
System.out.println(" :");
key = scanner.next(); //
i = SL.SLFindByCont(SL, key);
pdata = SL.SLFindByNum(SL, i);
if (pdata != null) {
System.out.println(" " + key + " :" + pdata.key + " " + pdata.name + " " + pdata.age);
}
}
}
// :
!
( )
18
( )
30
( )
30
，
:
18
30
:
1
1 : 18
:
: 30코드 가 길 어서 개발 도구 에 넣 어 보 는 것 을 권장 합 니 다.
4. 순서 구조의 단점:
4.1 노드 를 삽입 하고 삭제 할 때 대량의 데 이 터 를 이동 해 야 한다.
4.2 표 가 크 면 충분 한 저장 공간 을 분배 하기 어려워 서 메모리 분배 에 실패 할 때 가 있다.
12. 링크 구조
1. 링크 구조 란 무엇 입 니까? 동적 저장 분배 의 구조 형식 으로 필요 에 따라 동적 으로 신청 할 수 있 는 메모리 유닛 입 니 다.
2. 링크 구조의 구성:
데이터 부분: 실제 데이터 저장
주소 부분: 다음 노드 의 주 소 를 저장 합 니 다.
3. 장단 점
장점: 논리 연속 실제 주소 가 연속 되 지 않 고 대량의 데 이 터 를 저장 할 때 대량의 연속 공간 을 분배 할 필요 가 없다.
단점: 모든 노드 는 인용 변 수 를 추가 로 저장 하고 저장 공간 을 차지 해 야 합 니 다.
4. 링크 분류:
단일 체인 시트, 양 방향 링크, 단일 순환 링크, 다 중 체인 의 순환 링크
5. 코드 전시
import java.util.Scanner;
/**
* 1.
*/
//
class DATA {
String key; //
String name;
int age;
} //
//
class CLType { //
DATA nodeData = new DATA(); //
CLType nextNode; //
/**
*
* :
* 1.
* 2. head ,
* 3.
* 4. null
*/
CLType CLAddEnd(CLType head, DATA nodeData) {
CLType node, htemp;
if ((node = new CLType()) == null) { // new
System.out.println(" !");
return null;
} else {
node.nodeData = nodeData; //
node.nextNode = null; // , , null
if (head == null) { //
head = node;
return head;
}
htemp = head;
while (htemp.nextNode != null) { //
htemp = htemp.nextNode; // ,
}
htemp.nextNode = node; // ,
return head;
}
}
/**
*
* 1. ,
* 2. head
* 3. head
*/
CLType CLAddFirst(CLType head, DATA nodeData) {
CLType node;
if ((node = new CLType()) == null) {
System.out.println(" !");
return null;
} else {
node.nodeData = nodeData; //
node.nextNode = head; //
head = node; // ,
return head;
}
}
/**
*
*
*
*/
CLType CLFindNode(CLType head, String key) {
CLType htemp;
htemp = head;
while (htemp != null) {
//
if (htemp.nodeData.key.compareTo(key) == 0) {
return htemp;
}
htemp = htemp.nextNode; //
}
return null; //
}
/**
* ( )
* 1. ,
* 2. head ,
* 3. ,
*/
CLType CLInsert(CLType head, String findKey, DATA nodeData) {
CLType node, nodeTemp;
if ((node = new CLType()) == null) {
System.out.println(" !");
return null;
}
node.nodeData = nodeData; //
nodeTemp = CLFindNode(head, findKey); //
if (nodeTemp != null) {
node.nextNode = nodeTemp.nextNode; //
nodeTemp.nextNode = node; //
} else {
System.out.println(" !");
}
return head;
}
/**
*
* 1.
* 2.
* 3.
*/
int CLDelete(CLType head, String key) {
CLType node, hTemp; //node
hTemp = head;
node = head;
while (hTemp != null) {
if (hTemp.nodeData.key.compareTo(key) == 0) { // ,
node.nextNode = hTemp.nextNode; //
hTemp = null; //
return 1;
} else {
node = hTemp; //
hTemp = hTemp.nextNode; //
}
}
return 0; //
}
/**
*
*/
int CLLength(CLType head) {
CLType htemp;
int Len = 0;
htemp = head;
while (htemp != null) { //
Len++;
htemp = htemp.nextNode;
}
return Len;
}
/**
*
*/
void CLAllNode(CLType head) {
CLType htemp;
DATA nodeData;
htemp = head;
System.out.println(" " + CLLength(head) + " , :");
while (htemp != null) {
nodeData = htemp.nodeData; //
System.out.println(nodeData.key + " " + nodeData.name + " " + nodeData.age);
htemp = htemp.nextNode;
}
}
}
//-------------------------------------------------------------------------
/**
* 2.
*/
public class LInkedTable {
public static void main(String[] args) {
//
CLType node, head = null;
CLType CL = new CLType();
String key, findKey;
Scanner input = new Scanner(System.in);
System.out.println(" . , ( )");
//
do {
DATA nodeData = new DATA();
nodeData.key = input.next();
if (nodeData.key.equals("0")) {
break; // 0 ,
} else {
nodeData.name = input.next();
nodeData.age = input.nextInt();
head = CL.CLAddEnd(head, nodeData); //
}
} while (true);
CL.CLAllNode(head); //
System.out.println(" , :");
findKey = input.next();
System.out.println(" :( ( 0) )");
DATA nodeData = new DATA();
nodeData.key = input.next();
nodeData.name = input.next();
nodeData.age = input.nextInt();
CL.CLInsert(head, findKey, nodeData);
CL.CLAllNode(head); //
System.out.println(" , :");
key=input.next();
CL.CLDelete(head,key);
CL.CLAllNode(head); //
System.out.println(" , :");
key=input.next();
node = CL.CLFindNode(head, key);
if(node==null){
System.out.println(" "+key+" !");
}else{
nodeData = node.nodeData;
System.out.println(" :"+nodeData.key+" "+nodeData.name+" "+nodeData.age);
}
}
}
// :
. , ( )
1
18
2
20
3
30
0
3 , :
1 18
2 20
3 30
, :
2
:( ( 0) )
4
32
4 , :
1 18
2 20
4 32
3 30
, :
4
3 , :
1 18
2 20
3 30
, :
3
:3 306. 눈 으로 만 보 는 것 보다 손 을 쓰 는 것 이 낫다.
따뜻 한 알림: 코드 를 글 에 놓 으 면 너무 큰 폭 을 차지 하 는 것 같 습 니 다. 뒤의 긴 코드 는 github 에 놓 을 것 입 니 다. 필요 한 파트너 가 스스로 참고 지 도 를 다운로드 하 기 를 바 랍 니 다.
Github 주소:https://github.com/flakkaqi/DataStructure_and_Algorithms.git
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
